你真的会做 2 Sum 吗？

向右看齐 2022-11-29 11:36 214阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

2 Sum 这题是 Leetcode 的第一题，相信大部分小伙伴都听过的吧。

作为一道标着 Easy 难度的题，它真的这么简单吗？

我在之前的刷题视频里说过，大家刷题一定要吃透一类题，为什么有的人题目做着越来越少，有的人总觉得刷不完的题，就是因为没有分类吃透。

单纯的追求做题数量是没有意义的，Leetcode 的题目只会越来越多，就像高三时的模考试卷一样做不完，但分类总结，学会解决问题的方式方法，才能遇到新题也不手足无措。

## 2 Sum ##

![format_png 2][]

这道题题意就是，给一个数组和一个目标值，让你在这个数组里找到两个数，使得它俩之和等于这个目标值的。

比如题目中给的例子，目标值是 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)

喏，这速度不太行诶。

![format_png 3][]

### 方法二 ###

那在我学了 `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<Integer, Integer> 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%`

![format_png 4][]

### 拓展 ###

这是最基本的 `2 Sum` 问题，这个题可以有太多的变种了：

*  如果这个数组里有不止一组结果，要求返回所有组合，该怎么做？
 *  如果这个数组里有重复元素，又该怎么做？
 *  如果这个数组是一个排好序了的数组，那如何利用这个条件呢？- Leetcode 167
 *  如果不是数组而是给一个 `BST` ，该怎么在一棵树上找这俩数呢？- Leetcode 653

...

这里讲一下排序数组这道题，之后会在 `BST` 的文章里会讲 653 这题。

### 排序数组 ###

![format_png 5][]

我们知道排序算法中最快的也需要 `O(nlogn)`，所以如果是一个 `2 Sum` 问题，那没必要专门排序，因为排序会成为运算的瓶颈。

但如果题目给的就是个排好序了的数组，那肯定要好好收着了呀！

因为当数组是排好序的时候，我们可以进一步优化空间，达到 `O(n)` 的时间和 `O(1)` 的空间。

该怎么利用排好序这个性质呢？

那就是说，在 `x` 右边的数，都比 `x` 要大；在 `x` 左边的数，都比 `x` 要小。

*  如果 `x + y > target`，那么就要 `y` 往左走，往小的方向走；
 *  如果 `x + y < target`，那么就要 `x` 往右走，往大的方向走。

![format_png 6][]

这也就是典型的 `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 ##

![format_png 7][]

`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<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> 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` 问题啦。

![format_png 8][]

这一题如果只是 `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]` 并没有区别，所以我们要**限制第二组的两个数要在第一组的两个数之后**哦。

![format_png 9][]

看下代码吧：

class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
                Set<List<Integer>> set = new HashSet<>();
        Map<Integer, List<List<Integer>>> 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<List<Integer>> 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<List<Integer>> prevPairs = map.get(target - currSum);
            if(prevPairs == null) {
                continue;
            }
            for(List<Integer> 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` 相关的所有问题啦，如果有收获的话，记得给我点个赞哦～

\---

爱分享，爱开源，**GitHubPorn** 现已正式上线！专注于为大家分享优质的计算机学习资源与开发者工具。

如果今天的推荐符合你的口味，请在文章点赞，以表示对我的支持，你们的点赞和转发关注，是我持续更新的动力^\_^

[format_png]: /images/20221124/ced068df9fa24740a32034452f685fca.png
[format_png 1]: /images/20221124/70bcdeea7f264a1b8a643077371ee375.png
[format_png 2]: /images/20221124/c57ddf64417a4f528b08ee87677f9f33.png
[format_png 3]: /images/20221124/92f90b5ab41b4f418b1483497a1b0efa.png
[format_png 4]: /images/20221124/1ed429fa323d47b69497a06d3914f895.png
[format_png 5]: /images/20221124/09cfbf72f2b74632819375ce662cc1b3.png
[format_png 6]: /images/20221124/606e8fc0145c46c4bd7f8b5fe5110b1d.png
[format_png 7]: /images/20221124/1943cb9e4f114c78bdbceda1376c403b.png
[format_png 8]: /images/20221124/42e5634c233f48d18c6a40840122e2fa.png
[format_png 9]: /images/20221124/f4314ff2797545f7a594f39f24a28554.png