题目描述

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

给定一个有n个整数的数组S, 判断是否存在a, b, c三个元素满足a + b + c = 0? 找到数组中所有满足和为零的三个数（数组中不能有重复的三个数） 。

代码及注释

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 最终结果可能是多个vector
        vector<vector<int>> result;
        // 数组长度小于3，无结果
        if(nums.size()<3)   return result;
        // 先对数组进行排序
        sort(nums.begin(),nums.end());
        // 可修改target，使3sum最终结果为多少
        const int target = 0;
        // last是个迭代器，赋予auto类型
        auto last = nums.end();
        // i指针最外层循环
        for(auto i = nums.begin();i<last-2;++i){
            // 内部循环初始j指针是i后面一个
            auto j = i+1;
            // 当i变化时，如果重复则跳过。
            if(i>nums.begin() && *i == *(i-1))   continue;
            // 内部循环初始k是最后一个位置
            auto k = last-1;
            // 停止条件j<k
            while(j<k){
                if(*i + *j + *k <target){
                    ++j;
                    // 指针每次变化都需要检验是否重复
                    while(*j == *(j-1) && j<k)   ++j;
                }
                else{
                    if(*i + *j + *k > target){
                        --k;
                        while(*k == *(k+1) && j<k)   --k;
                    }
                    else{
                        result.push_back({*i,*j,*k});
                        ++j;
                        --k;
                        while(*j == *(j-1) && *k == *(k+1) && j<k)  ++j;
                    }
                }

            }
        }

        return result;
    }
};

分析

假定满足条件的三个数为a,b,c，这三个数索引分别为i, j, k。
先排序，
从数组的头确定一个数a，b的索引比a大1，c为数组的尾，有三种情况

a + b + c = target 则i++ k-- 并把这三个数记录下来
a + b + c < target 说明选的值还太小，j增大微调，则j++
a + b + c > target 说明选的值太大，k减小调整，则k--
终止条件b < c。
相当于确定两个，动一个