你真的会做 2 Sum 吗？
2 Sum 这题是 Leetcode 的第一题，相信大部分小伙伴都听过的吧。
作为一道标着 Easy 难度的题，它真的这么简单吗？
我在之前的刷题视频里说过，大家刷题一定要吃透一类题，为什么有的人题目做着越来越少，有的人总觉得刷不完的题，就是因为没有分类吃透。
单纯的追求做题数量是没有意义的，Leetcode 的题目只会越来越多，就像高三时的模考试卷一样做不完，但分类总结，学会解决问题的方式方法，才能遇到新题也不手足无措。
2 Sum
这道题题意就是，给一个数组和一个目标值，让你在这个数组里找到两个数，使得它俩之和等于这个目标值的。
比如题目中给的例子，目标值是 9，然后数组里 2 + 7 = 9，于是返回 2 和 7 的下标。
方法一
在我多年前还不知道时空复杂度的时候，我想这还不简单嘛，就每个组合挨个试一遍呗，也就是两层循环。
后来我才知道，这样时间复杂度是很高的，是 O(n^2)；但另一方面，这种方法的空间复杂度最低，是 O(1)。
所以，面试时一定要先问面试官，是希望优化时间还是优化空间。
一般来说我们追求优化时间，但你不能默认面试官也是这么想的，有时候他就是想考你有没有这个意识呢。
如果一个方法能够兼具优化时间和空间那就更好了，比如斐波那契数列这个问题中从递归到 DP 的优化，就是时间和空间的双重优化，不清楚的同学后台回复「递归」快去补课～
我们来看下这个代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1};
}
}
时间复杂度：O(n^2) 空间复杂度：O(1)
喏，这速度不太行诶。
方法二
那在我学了 HashMap 这个数据结构之后呢，我又有了新的想法。
HashMap 或者 HashSet 的最大优势就是能够用 O(1) 的时间获取到目标值，那么是不是可以优化方法一的第二个循环呢？
有了这个思路，假设当前在看 x，那就是需要把 x 之前或者之后的数放在 HashSet 里，然后看下 target - x 在不在这个 hashSet 里，如果在的话，那就匹配成功～
诶这里有个问题，这题要求返回这俩数的下标，可是 HashSet 里的数是无序的...
那就用升级版——HashMap 嘛～～还不了解 HashMap 的原理的同学快去公众号后台回复「HashMap」看文章啦。
HashMap 里记录下数值和它的 index 这样匹配成功之后就可以顺便得到 index 了。
这里我们不需要提前记录所有的值，只需要边过数组边记录就好了，为了防止重复，我们只在这个当前的数出现之前的数组部分里找另一个数。
总结一下，
HashMap里记录的是下标i之前的所有出现过的数；对于每个 nums[i]，我们先检查target - nums[i]是否在这个map里；如果在就直接返回了，如果不在就把当前 i的信息加进map里。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
res[0] = map.get(target - nums[i]);
res[1] = i;
return res;
}
map.put(nums[i], i);
}
return res;
}
}
时间复杂度：O(n) 空间复杂度：O(n)
喏，速度提升至 beat 99.96%
拓展
这是最基本的 2 Sum 问题，这个题可以有太多的变种了：
如果这个数组里有不止一组结果，要求返回所有组合，该怎么做？
如果这个数组里有重复元素，又该怎么做？
如果这个数组是一个排好序了的数组，那如何利用这个条件呢？- Leetcode 167
如果不是数组而是给一个
BST，该怎么在一棵树上找这俩数呢？- Leetcode 653
...
这里讲一下排序数组这道题，之后会在 BST 的文章里会讲 653 这题。
排序数组
我们知道排序算法中最快的也需要 O(nlogn)，所以如果是一个 2 Sum 问题，那没必要专门排序，因为排序会成为运算的瓶颈。
但如果题目给的就是个排好序了的数组，那肯定要好好收着了呀！
因为当数组是排好序的时候，我们可以进一步优化空间，达到 O(n) 的时间和 O(1) 的空间。
该怎么利用排好序这个性质呢？
那就是说，在 x 右边的数，都比 x 要大；在 x 左边的数，都比 x 要小。
如果
x + y > target，那么就要y往左走，往小的方向走；如果
x + y < target，那么就要x往右走，往大的方向走。
这也就是典型的 Two pointer 算法，两个指针相向而行的情况，我之后也会出文章详细来讲哒。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1}; //Your returned answers are not zero-based.
} else if (sum < target) {
left ++;
} else {
right --;
}
}
return new int[]{-1, -1};
}
}
3 Sum
3 Sum 的问题其实就是一个 2 Sum 的升级版，因为 1 + 2 = 3 嘛。。
那就是外面一层循环，固定一个值，在剩下的数组里做 2 Sum 问题。
反正 3 Sum 怎么着都得 O(n^2) ，就可以先排序，反正不在乎排序的这点时间了，这样就可以用 Two pointer 来做了。
还需要注意的是，这道题返回的是数值，而非 index，所以它不需要重复的数值——The solution set must not contain duplicate triplets.
class Solution {
public List> threeSum(int[] nums) {
List> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i + 2 < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
// skip same result
continue;
}
int j = i + 1;
int k = nums.length - 1;
int target = -nums[i];
while (j < k) {
if (nums[j] + nums[k] == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) {
j++; // skip same result
}
while (j < k && nums[k] == nums[k + 1]) {
k--; // skip same result
}
} else if (nums[j] + nums[k] > target) {
k--;
} else {
j++;
}
}
}
return res;
}
}
4 Sum
最后就是 4 Sum 问题啦。
这一题如果只是 O(n^3) 的解法没什么难的，因为就是在 3 Sum 的基础上再加一层循环嘛。
但是如果在面试中只做出 O(n^3) 恐怕就过不了了哦?
这 4 个数，可以想成两两的 2 Sum，先把第一个 2 Sum 的结果存下来，然后在后续的数组中做第二个 2 Sum，这样就可以把时间降低到 O(n^2) 了。
这里要注意的是，为了避免重复，也就是下图的 nums[x] + nums[y] + nums[z] + nums[k] ，其实和 nums[z] + nums[k] + nums[x] + nums[y] 并没有区别，所以我们要限制第二组的两个数要在第一组的两个数之后哦。
看下代码吧：
class Solution {
public List> fourSum(int[] nums, int target) {
Set> set = new HashSet<>();
Map>> map = new HashMap<>();
Arrays.sort(nums);
// 先处理第一对，把它们的sum存下来
for(int i = 0; i < nums.length - 3; i++) {
for(int j = i + 1; j < nums.length - 2; j++) {
int currSum = nums[i] + nums[j];
List> pairs = map.getOrDefault(currSum, new ArrayList<>());
pairs.add(Arrays.asList(i, j));
map.put(currSum, pairs);
}
}
// 在其后做two sum
for(int i = 2; i < nums.length - 1; i++) {
for(int j = i + 1; j < nums.length; j++) {
int currSum = nums[i] + nums[j];
List> prevPairs = map.get(target - currSum);
if(prevPairs == null) {
continue;
}
for(List pair : prevPairs) {
if(pair.get(1) < i) {
set.add(Arrays.asList(nums[pair.get(0)], nums[pair.get(1)], nums[i], nums[j]));
}
}
}
}
return new ArrayList<>(set);
}
}
好啦，以上就是 2 Sum 相关的所有问题啦，如果有收获的话，记得给我点个赞哦～
往期推荐
后台回复 学习资料 领取学习视频
如有收获，点个在看，诚挚感谢