[LeetCode-py-0001] Two Sum

原文

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:

1
2
3
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

分析

方法一

首先最简单的就是穷举法, 拿第一个数和其他数求和判断, 然后再拿第二个和后面的其他数求和判断, 暴力代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if i != j and nums[i] + nums[j] == target:
return [i, j]


if __name__ == '__main__':
nums = [2, 7, 11, 15]
print(Solution().twoSum(nums, 9))

方法二

另一种方式是利用字典, 将遍历过的数以 value:index 形式存入字典, 然后每次计算 target-value 的值是否在字典里, 如果在, 说明这两个数满足条件;

1
2
3
4
5
6
7
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(nums)):
n = target - nums[i]
if n in dic:
return [dic[n], i]
dic[nums[i]] = i

对比

方法时间复杂度空间复杂度
方法一$O(n^2)$$O(1)$
方法二$O(n)$$O(n)$

代码

LeetCode-py


--------------------本文至此结束  感谢您的阅读--------------------

本文标题:[LeetCode-py-0001] Two Sum

文章作者:Memento

发布时间:2019年04月23日 - 09:04

最后更新:2019年04月24日 - 19:04

原始链接:https://memento.net.cn/post/16695df5.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Memento wechat
欢迎您扫一扫上面的微信公众号, 订阅阁主公众号!
坚持原创技术分享, 您的支持将鼓励我继续创作