Leetcode 1 Two Sum

发表于 |

给定一个数组nums，一个目标值target，在数组找两个数满足这两个数的和为target。
返回这两个数在nums中的下标。

example:
nums = [2,7,11,15]
target = 9
return [0,1]

题意分析：
在数组中寻找两个数a,b，使得a+b = target，返回a,b的下标

思路分析：>
这是一道经典的在数组中找和为定值的题目。通常这种题目有以下几种解法：

  1. 先将数组进行排序，然后用双指针遍历。（time: O(nlogn), space: O(1)）
  2. 将遍历过的数a全部记录下来，然后对正在遍历的数b进行判断，判断target - b是否已经遍历过。（time: O(n), space: O(n)）

以上两种解法同样适用于找a+b+c=target的问题（3Sum），只是具体操作时会有一点不同。

再来看这道题，因为我们需要返回下标，如果我们使用第一种方法会将本来的下标打乱（当然你可以新开一个空间专门记录下标，但是这白浪费O(n)的空间，丧失了排序的优势），所以我们直接选择第二种方法

1
2
3
4
5
6
7
8
9
# 28ms, beats 65.80%
class Solution(object):
    def twoSum(self, nums, target):
        vis = {}
        for i in range(len(nums)):
            if target - nums[i] in vis:
                # 因为题目保证一定有解，所以可以直接返回
                return [vis[target- nums[i]], i]
            vis[nums[i]] = i