leetcode_001_towsum

发表于 | 更新于: | 分类于 |

leetcode-001-towsum 两数之和

1. 题目

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

2. 解

  • 首先想到用两个for循环，依次相加，判断等于target时返回index。但是这种方法存在重复计算的问题。这种思路是找A + B = target中的A和B两个数。

换一种思路，从找两个数（A和B）转换为找一个数（B）：

  • 用一个for循环遍历数组中的元素，拿到A，那么B肯定也在数组中，并且target - A = B。此时给一个字典，key存target - A也就是B，value存index（这个index是A的）。在字典中找B。这样计算结果就保存在字典中，只需要计算一次即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    在遍历数组的过程中：

    如果当前元素（A）不在字典中：kay存target - A（即B），value存A的index；

    如果当前元素在字典中：那么就找到了B，返回当前元素（B）的index和字典中key为B的value，这个value是A的index。

    class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            dict_diff = {}
            for index in range(len(nums)):
                if nums[index] in dict_diff:
                    return [dict_diff[nums[index]], index]
                else:
                    dict_diff[target - nums[index]] = index