1. 两数之和

发表于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟

我敢说，来到 LeetCode 的人，大多数会从这道题开始，简直就是算法界的 Hello World 好不好，特别简单，直接就能做出来，自我感觉良好，可以继续了。但是，废渣如我，在这种题目上还是掉坑了，也是没谁了吧……

题目是这样的：

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

引用自 LeetCode 第 1 题

是不是超级简单啊，上手就干，按照以前我肯定会想得很复杂，用最最直接的法子，先拿出第一个，然后逐个遍历后面的，看哪个和第一个加起来等于目标，现在我已经有了极大的进步，知道用减法了，先拿出第一个数字和目标做差，然后在剩下的数字里搜索第二个。对的，我就是这么废。这道题目做了不知道多少次后，我终于记住了，应该用减法把题目转化成简单的搜索。我写了下面这个东西：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = 0
        while i < len(nums) - 1 :
            j = i + 1
            while j < len(nums) :
                if nums[j] == target - nums[i] :
                    return [i, j]
                j += 1
            i += 1

测试了几个用例以后，我信心满满，直接点击了提交，然后，现实给了我无情的暴击，FAIL，超时了，我一看，给我传入了一个 List，内容能铺满我 5K 的 27 寸屏幕，简直……

原来坑在这里啊，我就说不会这么简单，其实我以前肯定做过这题目了。但是早就忘记了。此时，我再次头脑一片空白，不知道从哪里入手解决这个性能问题。然后，我就看了答案，1s 后我就恍然大悟，想起来了！

这个题目表面上用的数据结构是 List，线性列表，看起来又是一个在线性列表上的搜索的题目，但是隐藏了一个性能的问题。

我出于比本能多了一丁点智能的能力写出的代码，很显然是一个 O(n^2) 的算法，因为要循环两次，这其实就是一个暴力解法。

那么怎么才能降低算法的时间复杂度呢？注意：超时就是时间复杂度过高的意思。所以，看到超时错，我们基本要分析的就是时间复杂度。

然后一个很自然的思路，就是空间换时间，从而降低时间复杂度。看我说得头头是道，临场还是屁也想不出来，所以，你想出来了，就可以很开心了。多么自然而然的思路，为啥我就没有呢？

这里就多了一个知识点，这道题就迁移到了另外一个知识点，什么数据结构，可以用空间换时间？OK，就是哈希（Hash），在 PHP 里叫 array，在 Python 里是 dict，在 Java 里是 Map，反正都差不多。

因为原理都是用到 Hash，查询的复杂度是常数 O(1)，当然，作为代价会给每个元素开一个桶。既然看懂了，怎么能不跃跃欲试？我写出了这个：

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numdic = {}
        for i in range(len(nums)):
            numdic[nums[i]] = i
            other = target - nums[i]
            if other in numdic and numdic[other] != i:
                return [i, numdic[other]]

先把一个数字放进一个哈希表，然后，搜索另一半在不在里面，在的话，立马返回，然后重复这个过程。FAIL，有个用例是[3,3]，目标是 6，竟然立刻击破了我的算法。弱爆了。忘记两个数字一样的问题了。就算你知道了正确的方向，还是要心里想明白才行啊，比如忘记了两个数字一样的情况。

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numdic = {}
        for i in range(len(nums)):
            other = target - nums[i]
            if other in numdic:
                return [i, numdic[other]]
            numdic[nums[i]] = i

再改了一下，终于写出来了，就是要先搜索，再放进哈希表，就可以解决两个重复的问题。

薄弱知识点总结：

  1. Python 的 for 遍历语法，不熟悉；
  2. 哈希表的特点不熟悉；
  3. 空间换时间的常见套路不熟悉；