LeetCode 第1题：Two Sum

题目

给出一个整数数组，找出其中的两个整数，使相加等于指定整数，并返回这两个整数的索引。

假设每组输入只有一种解法，并且不能重复使用同一个元素。

举例：

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

因为 nums[0] + nums[1] = 2 + 7 = 9,
所以返回 [0, 1].

思路

最简单也是最直接的想法就是两重循环直接遍历计算就能得到结果，时间复杂度为 。
但这肯定不是最优解。

题目中提到只会有一种解法，那就意味着不会有重复的整数，不然就会有多解。
既然没有重复的，那用一个哈希来存储数据就最合适了，整数为键，索引为值。
那我们要找两个整数的索引就很方便了，在遍历数组的时候，检查和目标的差值是否在哈希中，有的话就是答案了。

Go 实现

func twoSum(nums []int, target int) []int {
    h := make(map[int]int)
    for i, value := range nums {
        if wanted, ok := h[value]; ok {
            return []int{wanted, i}
        } else {
            h[target-value] = i
        }
    }
    return nil
}

运行时间：4ms，超过100%的 golang 提交。

Python3 重写

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h = {}
        for i, value in enumerate(nums):
            if value in h:
                return [h[value], i]
            else:
                h[target - value] = i
        return None

运行时间：52ms，超过47.04%的 python3 提交。

Python3 优化

从上面的数据上看效率有点低，应该是 enumerate 生成迭代器效率稍差，所以换用 range(len(...)) 的写法。

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

运行时间：36ms，超过99.71%的 python3 提交。