1. 两数之和

题目

两数之和

分析

这道题目给我们一个数组，数组里面全是整数，然后再给我们一个数字 target，需要我们求出在这个数组中哪两个数字的和正好是 target。注意，你不能重复利用这个数组中同样的元素，指的是每一个位置上的数字只能被使用一次，比如数组 [3,3,5]，你可以使用第一个和第二个 3，但是你不能使用第一个 3 两次。

解题方案

思路 1: 暴力解法，双重循环遍历

时间复杂度: $O(n^2)$ , 空间复杂度: $O(1)$

外层循环从数组中取出下标为 i 的元素 num[i]，内层循环取出 i 之后的元素 nums[j] 一一与下标为 i 的元素进行相加操作，判断结果是否为 target。

为什么内层循环要取 i 之后的元素的元素呢？因为如果第二轮取得 i 之前的数的话，其实我们之前就已经考虑过这种情况了（即外层循环已经遍历过此时内层循环的这个数字）。（需要得到的是组合而不是排列）

题目只要求找到一种，所以一旦找到直接返回。时间复杂度中的 N 代表的是 nums 列表的长度。

代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 第一轮遍历
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // 第二轮遍历不能重复计算了
            for (int j = i + 1; j < length; j++) {
                if (nums[i] + nums[j] == target) {
                    // 注意 leetcode 中要求返回的是索引位置
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

思路 2：考虑牺牲空间来换取时间

时间复杂度: $O(n)$ , 空间复杂度: $O(n)$

第二层 for 循环无非是遍历所有的元素，看哪个元素等于 target-nums[i] ，时间复杂度为 $O(n)$ 。

有没有一种方法，不用遍历就可以找到元素里有没有等于 target-nums[i] 的？

hash table ！！！

为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 $O(n)$ 降低到 $O(1)$ 。哈希表正是为此目的而构建的，它支持以近似恒定的时间进行快速查找。我用 “近似” 来描述，是因为一旦出现冲突，查找用时可能会退化到 $O(n)$ 。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 $O(1)$ 。

我们可以把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value 。

这样只需判断 target-nums[i] 在不在 hash 的 key 里就可以了，而此时的时间复杂度仅为 $O(1)$ ！

需要注意的地方是，还需判断找到的元素不是当前元素，因为题目里讲一个元素只能用一次。

因此我们有了下面的步骤：

建立字典 lookup 存放第一个数字，并存放该数字的 index；
判断 lookup 中是否存在 target - 当前数字 cur，则当前值 cur 和某个 lookup 中的 key 值相加之和为 target；
如果存在，则返回： target - 当前数字 cur 的 index 与当前值 cur 的 index；
如果不存在则将当前数字 cur 为 key，当前数字的 index 为值存入 lookup。

代码：

class Solution2 {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 将原本为两个目标值切换为一个目标值，只需要每次从 map 中寻找目标值即可
            int num = target - nums[i];
            if (map.containsKey(num)) {
                return new int[]{map.get(num), i};
            }
            // 每次遍历过的值都存储到 map 中，这样之后就能从 map 中寻找需要的目标值
            map.put(nums[i], i);
        }
        return null;
    }
}

总结

拿到题目之后我们可以用最朴素和最暴力的方式来解答。这样做虽然没有什么问题，但在用最简单的方式去解答完成之后，多想想怎么可以去优化一下解答方式，培养 “最优” 思维。习惯这样想之后你的代码才会越来越优秀；

当然。不是任何时候 “最优” 即最合适，我们也要考虑一下条件限制的问题，在各种环境中找出最合适的方式才是真正的 “最优”；

常见的减小时间复杂度的方式有：用空间来弥补多余的计算。

时间复杂度从 $O(n^2)$ 降为 $O(n)$ 的时候，对 hash 的应用，有眼前一亮的感觉。

拓展

数组应用场景
散列表原理

Java 相关

新建有值数组的方式

new int[]{i, j};

新建 HashMap，泛型方式

HashMap<Integer, Integer> hashMap = new HashMap<>();

哈希表中是否存在某个键

hashMap.containsKey(key); // return bool

根据键获取哈希表的值

hashMap.get(key);

向哈希表中添加元素

hashMap.put(key, value);