LeetCode实战015 三数之和

原题链接

题目描述

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目分析

之前我们做过两数之和TwoSum，这道题可以看做是它的升级版。如果用同样的思路，以暴力循环求解，确实可以得到答案，但是复杂度太高了，两个数求和复杂度是，可以接受。求三个数之和是，会超时，并且还会有去重的问题需要考虑，更别提还有四数之和的求解了。

所以我们要想办法减少迭代，如果我们对给定的输入先进行一次排序的话，那么我们就可以利用单调性来逼近可行解，同时也一定程度上解决了重复的问题。

解法：夹逼法

我们可以先对输入数据进行排序，使得数据单调递增（当然，递减也是可以的，我不歧视递减，233）。此时，我们可以先通过遍历找到元素i, 随后在剩余元素（下文称作“子序列”）中找到j和k，使得i+j+k=0，即j+k=-i。

在寻找j和k的过程中，我们可以将二者的初值分别赋为子序列最左端、最右端的元素，分别对应子序列中的最小值和最大值。每次迭代，我们将j和k求和，并与-i作比较，每次比较，可能存在3种情况：

1. 若j+k<-i，说明j需要增大
2. 若j+k>-i，说明k需要减小
3. j+k=-i,刚好合适，找到了一个可行解{i, j, k}

你可能不理解为什么有些情况下j要增大，而不是k减小，反之也是同理，这里贴一张图帮助大家理解：

代码

编写过程中注意去重即可。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        if (nums.size() < 3)
            return res;

        sort(nums.begin(), nums.end());//排序

        //左右夹逼
        for (int i = 0; i < nums.size(); i++) {
            int target = nums[i];
            if (i > 0 && nums[i] == nums[i - 1])//对i的去重
                continue;
            int j = i + 1, k = nums.size() - 1;
            while (j < k) {
                if (nums[j] + nums[k] < -target) {
                    j++;
                    while (nums[j] == nums[j - 1] && j < k)//对j的去重
                        j++;
                }
                else if (nums[j] + nums[k] > -target) {
                    k--;
                    while (nums[k] == nums[k + 1] && j < k)//对k的去重
                        k--;
                }
                else {
                    res.push_back({ nums[i], nums[j], nums[k] });
                    j++, k--;
                    while (nums[j] == nums[j - 1] && j < k)//j,k都去重
                        j++;
                    while (nums[k] == nums[k + 1] && j < k)
                        k--;
                }
            }
        }
        return res;
    }
};

复杂度分析

• 时间复杂度
• 空间复杂度