力扣 15. 三数之和

力扣题目链接

给你一个包含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]
输出：[]

双指针法，时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度取决于满足条件的三元组数目：

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;

        sort(nums.begin(), nums.end()); // 双指针法首先要将数据进行排序

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) return result; // 三个元素中的最小值已经大于0了 已经无法凑出和为0的三元组了

            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重 {0, 0, 0, 0}

            int left = i + 1;
            int right = nums.size() - 1;
            
            while (right > left) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    --right;
                    while (left < right && nums[right + 1] == nums[right]) --right; // 去重 {-2, 0, 0, 2, 2}
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    ++left;
                    while (left < right && nums[left - 1] == nums[left]) ++left; // 去重 {-2, 0, 0, 2, 2}
                } else {
                    result.push_back(vector{nums[i], nums[left], nums[right]});

                    ++left;
                    while (left < right && nums[left - 1] == nums[left]) ++left;

                    --right;
                    while (left < right && nums[right + 1] == nums[right]) --right;
                }
            }
        }

        return result;
    }
};

实际上当nums[left]去重后，原来重复的nums[right]自然也会自动被剪枝。

比如{-2, 0, 0, 2, 2}，其实第二个0被剪枝后无需再对2进行去重，由此可以进行改进。改进后执行用时和内存消耗均有改善，但是复杂度没有变化：

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i - 1] == nums[i]) continue;

            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                while (left < right && left > i + 1 && nums[left - 1] == nums[left]) left++;

                while (left < right && nums[i] + nums[left] + nums[right] > 0) right--;

                if (left < right && nums[i] + nums[left] + nums[right] == 0) {
                    result.push_back(vector{nums[i], nums[left], nums[right]});
                }
                ++left;
            }
        }

        return result;
    }
};