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]]

已知条件

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

解题方案

本题要求取得所有和为0的三元组，并且不能重复，因此选择对数组排序后，通过双指针法遍历数组，寻找所有不重复的和为0的三元组。需要注意各层循环的条件以及左右指针移动的条件。
循环条件：

• 遍历指针由nums.begin()循环至nums.end()-3
• 左右指针分别从i+1和nums.end()-1开始，移动至重合

指针移动条件：

• 遍历指针i>nums.begin()且与i-1处元素相等时i++
• 左指针left>i+1且与left-1处值相等时left++
• 右指针right<nums.end()-1且与right+1处的值相等时right--
• 三个指针处的值和小于0时left++
• 三个指针处的值和大于0时right--

该方法时间复杂度O(n^2)
C++代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        auto end = nums.end();
        auto start = nums.begin();
        vector<int>::iterator i, left, right;
        if (nums.size()<3) return result;
        sort(nums.begin(), nums.end());
        for (i=start; i!=end-2 && *i<1; ++i) {
            if (i>start && *i==*(i-1)) continue;
            left = i+1;
            right = end-1;
            while (left!=right) {
                if (left>i+1 && *left==*(left-1)){
                    left++;
                    continue;
                }
                if (right<end-1 && *right==*(right+1)){
                    right--;
                    continue;
                }
                if (*i+*left+*right<0) {
                    left++;
                }
                else if (*i+*left+*right==0) {
                    result.push_back({*i, *left, *right});
                    left++;
                }
                else {
                    right--;
                }
            }
        }
        return result;
    }
};