三数之和

题目描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

解析：

求三数之和为0的本质上是求两数之和为某一值，但是这两个数是不相等的，并且不是固定的，存在重复值。

首先通过对数组进行排序，固定三个数中的最小值，然后依次求得每一个数可能的两数之和。

主要思想：排序+双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 先对数组进行排序，确定第一个元素
        std::vector<std::vector<int>> result;
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i<n; ++i){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            // 找到除去i之外的两数之和
            // 此处j取i+1是因为i是三个数中的最小值，为固定的
            int j = i + 1, k = n - 1;
            // 两数之和的双指针求法
            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum>0) --k;
                else if(sum<0) ++j;
                else{
                    result.push_back({nums[i], nums[j], nums[k]});
                    // 跳过j，k的重复项目！！
                    for(++j; j<k&&nums[j] == nums[j-1]; ++j);
                    for(--k; k>j&&nums[k] == nums[k+1]; --k);
                }
            }
        }
        return result;
    }
};