题目内容

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

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

示例

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示

0 <= nums.length <= 3000
$-10^5$ <= nums[i] <= $10^5$

题解

我们可以使用双指针算法进行求解。

首先要明确，使用双指针算法的前提是有序，所以必须在使用之前对nums进行排序。

然后，假设有指针i、j、k，我们有如下思想：

为了最大限度减少重复的情况，我们可以规定i < j < k。

我们可以寻找满足nums[i]+nums[j]+nums[k] ≥ 0，因此当固定指针i时，当j指针往右移动时，因为数组有序，所以k指针一定往左移动，从中求出满足nums[i]+nums[j]+nums[k] = 0的情况。

注意，为了防止不重复，需要判断指针j的位置上的数值与下一个位置的数值是否一致，如果一致，则继续跳过。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //双指针算法的前提是有序。令i<j<k，固定i，然后对j和k进行双指针。将时间复杂度从n^3降为n^2。同时为了避免重复的三元组，需要对循环迭代的元素进行比较，若前一个元素和后一个元素一致，则跳过，一直到不是该元素为止。当然这个可行的前提依旧是需要有序！
        //i && nums[i] == nums[i - 1] 这种判断，可以将i==0的情况跳过，非常巧妙。
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(i && nums[i] == nums[i - 1] ) continue;
            for( int j = i + 1, k = nums.size() - 1; j < k; j++){
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;//j不是第一个数，同时数相同时，则跳过
                while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k--; //如果k的下一个数不与j重叠，且三数之和大于0，则一直往前
                if(nums[i]+nums[j]+nums[k] == 0){
                    res.push_back({nums[i],nums[j],nums[k]});
                }
            }
        }
        return res;
    }
};