Letcode 两数之和

题目
1
2
3
4
5
6
7
8
9
10
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
  1. 最简单的暴力解法

最容易想到的，但是内存耗时都是比较高的，这是一般人的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        index = 0
        ret = []
        ok = False
        for index in range(len(nums)):
            other = target - nums[index]
            start = index
            while start < len(nums) - 1:
                if nums[start + 1] == other:
                    ret.append(index)
                    ret.append(start + 1)
                    ok = True
                    break
                start += 1
            if ok:
                break
        return ret
  1. 简便解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_map = {}
        index = 0
        for num in nums:
            other = target - num
            if num_map.get(other) is not None:	# 注意0
                return [num_map.get(other), index]
            num_map[num] = index
            index += 1
        return [0, 0]

一次循环，把遍历过的每个数的差与当前数字的索引放入字典，后面如果有数字存在在字典中，则该index与字典中保存的index为结果

我真的是被自己蠢哭，花了一个小时，弄懂了两个算法；

深感有心无力，年龄大了，老程序员脑子不灵光了。