LeetCode15，比两数之和稍难一点的三数和，面试遇到你能搞定吗？

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天是周六，别光顾着玩，我们一起来看道算法题锻炼一下思维。

这道题也是面试中的常客，并且是LeetCode中非常经典的一道题，它就是三数之和。

但凡大家刷过LeetCode，哪怕只是打开题库看过的话，可能都会记得LeetCode第一题叫做两数之和，被誉为LeetCode中的abandon。大部分人都是看到这道题被劝退的。

今天这道题是两数之和的进阶版，两数之和名气比较大，在面试中的出镜率也很高。所以很多面试官会特意绕开两数之和，直接问这道题。

好了，我们废话不多说，直接来看题。

题意

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解法

借着这道题，我们再重温一下拿到题目之后的思考过程。首先还是老规矩，看完题意之后首先来看看数据范围。

数据范围当中隐藏的信息很多，还可以用来大致确定一下正确解答的复杂度，有很强的提示性。所以千万不要忽略，一定要仔细查看。

这道题当中数据的范围并不大，最多只有3000个数，每个数的范围是1e5，即使是三个数相加也不会超过int的范围，相对比较安全。其次最多只有3000个数，意味着

甚至是

都是可以接受的，相对来说，复杂度卡的不是非常死。

分析完了复杂度之后，我们可以尝试一下暴力的方法，看看暴力求解有没有什么问题，有哪些问题。绝大多数的问题暴力求解是不行的，但这并不是白费功夫。思考完了暴力解法之后，我们就能找到题目的难点。

也就是说第二个步骤是找到难点，几乎所有的算法题都是有难点的，这些难点基本上都是出题人刻意设置的。所以当我们不能或者是很难直接求解找到突破口的时候，不妨尝试一下难点分析，即想一想这题究竟难在哪里，真正困难的点在哪里。

以本题为例，我们要找到三个数，使得它们的和为0，并且要找出所有的组合。对于找所有解的问题来说，它的前提就是我们要能枚举所有可能构成解的可能性。在这道题当中，三个数的组合数量是

的量级，这是无法接受的。

那么难点也就找到了：我们要枚举的可能性太多，会导致复杂度无法接受。所以我们要做的就是想办法既能够枚举所有的可能性，又保证复杂度不会超过限制。

从理论上看，n个数当中找3个，无论如何也有

的量级，看似是无解的。但是我们仔细分析题目，可以找到突破口，这个突破口就是三个数和为0。既然三个数和为0，那么就对这三个数的组成有了一定的限制。很明显，这三个数不能全大于0，也不能全小于0。除非全为0，否则必须有正有负。进而我们可以想到，我们可以枚举其中一个值，在此基础上寻找另外两个值。

假设a+b+c=0，我们不妨设

。那么我们只需要枚举a，在此基础上，在大于等于a的部分当中寻找b和c的组合。由于

，那么a一定小于等于0。所以我们只需要在小于等于0的范围内枚举a，在大于等于a的范围内枚举b和c即可，这样就去掉了大部分无谓的组合，减小了搜索空间，提升了算法的效率。

到这里我们又很容易发现，无论是要在小于等于0的范围内枚举a，还是要在大于等于a的范围内枚举b和c，我们都需要数组元素有序。所以我们可以先对数组排序，使得数组中元素有序，接着在小于等于0的范围内枚举a，在a的右侧枚举b和c，寻找b+c=-a的组合。寻找b和c的过程，本质上是一个寻找两数和的问题。对于两数和的问题，我们已经比较熟悉了，我们当然可以使用map来维护，但由于元素已经有序了，我们也可以使用双指针直接来寻找。

完整代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        // 数组排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        // a+b+c=0, a <= b <= c, 枚举a
        for(int i = 0; i < n-2; i++) {
            // a大于0跳出
            if (nums[i] > 0) break;
            // 剪枝，去除重复搜索
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int l = i+1;
            int r = n-1;
            
            while (l < r) {
                // target = a + b + c, 根据target和0的关系决定是右移l或左移r
                int target = nums[i] + nums[l] + nums[r];
                if (target == 0) {
                    vector<int> cur {nums[i], nums[l], nums[r]};
                    ret.push_back(cur);
                    l++; r--;
                    // 跳过重复
                    while (l < r && nums[l] == nums[l-1]) l++;
                    // 跳过重复
                    while (l < r && nums[r] == nums[r+1]) r--;
                }else if (target > 0) r--;
                else l++;
            }
        }
        return ret;
    }
};

对于这道题而言，往简单了说可以很简单，一句话就能说清楚解法，即排序之后枚举第一个元素，将剩余问题转化成两数和问题求解。

但对于算法学习的过程来说，只是知道解法，不知道它的推导过程没有任何意义，下次碰到了还是做不出来。所以我们在做题的时候，千万不要一味图快，追求做题的数量和速度。而是要多思考，找找题目中的逻辑，锻炼思维，提升敏锐性，从而能很快找到突破口想到解法。

好了，关于这道题就先聊到这里，感谢大家的阅读。

喜欢本文的话不要忘记三连~