LC 1. 两数之和

题目描述

这是 LeetCode 上的 1. 两数之和 ，难度为 简单。

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6

输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6

输出：[0,1]

提示：

• $2 <= nums.length <= 10^3$
• -$10^9 <= nums[i] <= 10^9$
• -$10^9 <= target <= 10^9$
• 只会存在一个有效答案

---

朴素解法

由于我们每次要从数组中找两个数。

因此一个很简单的思路是：使用两重循环枚举下标 $i$ 和 $j$ ，分别代表要找的两个数。

然后判断 $nums[i] + nums[j] = target$ 是否成立。

另外为了防止得到重复的解，我们需要在第一层循环中让 $i$ 从 $0$ 开始，到 $n - 2$ 结束（确保能取到下一位数作为 j ）；在第二层循环中让 $j$ 从 $i + 1$ 开始，到 $n - 1$ 结束。

代码：

class Solution {
    public int[] twoSum(int[] nums, int t) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (t == nums[i] + nums[j]) return new int[]{i,j};
            }
        }
        return new int[]{};
    }
}

• 时间复杂度：两重循环，以复杂度是 $O(n^2)$
• 空间复杂度：$O(1)$

---

哈希表

首先，任何优化的思路都不外乎「减少重复」。

从朴素解法中可以知道，逻辑上我们是先定下来一个数，然后从数组中往后找另外一个值是否存在。但其实我们在找第二个数的过程中是重复扫描了数组多次。

举个例子，对于 nums = [2,3,8,4], target = 9 的样例，我们先确定下来第一个数是 2，然后从后扫描到最后一个数，检查是否有 7。发现没有，再决策第一个数为 3 的情况，这时候我们应该利用前一次扫描的结果来帮助我们快速判断是否存在 6，而不是再重新进行一次扫描。

这是直观的优化思路，不难想到可以使用哈希表进行存储。以数值为 key，数值的下标为 value。

当动手将想法转化为代码时，会发现如果先敲定第一个数，将后面的数加入哈希表，再进行下一位的遍历的时候，还需要将该数值从哈希表中进行删除。

代码：

class Solution {
    public int[] twoSum(int[] nums, int t) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i], b = t - a;
            if (map.get(a) == i) map.remove(a);
            if (map.containsKey(b)) return new int[]{i, map.get(b)};
        }
        return new int[]{};
    }
}

最坏情况下，每个数会对应一次哈希表的插入和删除。该解法本质是在循环过程中敲定第一个数，在哈希表中找该数后面是否存在第二个数。

这时候不妨将思路转换过来，遍历过程中敲定第二个数，使用哈希表在第二个数的前面去找第一个数。

具体的做法是，边遍历边存入哈希表，遍历过程中使用的下标 i 用作敲定第二个数，再从现有的哈希表中去找另外一个目标数（由于下标 $i$ 前面的数都被加入哈希表了，即在下标 $i$ 前面去找第一个数）。

class Solution {
    public int[] twoSum(int[] nums, int t) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i], b = t - a;
            if (map.containsKey(b)) return new int[]{map.get(b), i};
            map.put(a, i);
        }
        return new int[]{};
    }
}

从 LeetCode 上的执行时间来看，第一种哈希表做法是 4ms，而第二种哈希表的做法是 0ms（不足 1ms 的意思），快在了我们减少了哈希表的插入和删除操作。

但这只是常数级别上的优化，LeetCode 上的执行时间建议只作普通参考，还是要从算法的时空复杂度来分析快慢。

• 时间复杂度：第一种哈希表的做法会扫描数组两次，复杂度是 $O(n)$（忽略常数）；第二种做法只会对数组进行一遍扫描，复杂度是 $O(n)$
• 空间复杂度：两种做法都使用了哈希表进行记录，复杂度是 $O(n)$

---

其他

可以看到，我将原题目的入参 target 替换成了 t，但并不影响正确性，目的是为了提高编码速度。如果你也经常参与 LeetCode 周赛，就会发现这是一个常用的小技巧。

这个技巧，我希望你在第一题就掌握。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。