Two Sum

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 1 分钟

description

题目出处：leetcode

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.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解读

  • 给定一个包含多个数字的数组，返回两个值的下标，这两个值相加恰好等于target
  • 可确定的是，答案有且只有一个

Solution version alpha

  1. 创建一个字典，使用nums中的值作为key，下标作为value，这样可以迅速通过nums中的值获取其下标；
  2. 遍历nums中的值，如果target - nums中的数存在，则说明配对成功，这样直接通过这些值就能获取到下标作为返回值返回了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_map = {}
        for i, value in enumerate(nums):
            num_map[value] = i

        for value in nums:
            index = target - value
            if index != value and index in num_map:
                return [num_map[value], num_map[index]]

存在一个bug：当nums中有重复数字时，num_map只会存一个数字的下标，会导致信息丢失。如：
nums = [3, 3, 4, 5], target = 6
此时是获取不到正确的答案的。

Final solution

  1. 由于上一个步骤中，在构建字典过程中会导致同样值的key被覆盖，所以我们在构建字典过程中进行运算；
  2. 在构建字典过程中，遍历nums时，如果target-num已经存在于字典中，那么匹配成功，返回其相对应的下标即可；
  3. 否则，将当前的值加入到字典中，以备后续查找。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_map = {}
        for i in range(len(nums)):
            another = target - nums[i]
            if another in num_map:
                return [num_map[another], i]
            else:
                num_map[nums[i]] = i

0%