三数之和

题目描述
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。
例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)

解法

    //双指针
    //时间O（N*N） 空间O（1）
    vector<vector<int> > threeSum(vector<int> &nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        // 枚举 a
       for (int first = 0; first < n; first++) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
           //枚举b
           for (int second = first + 1; second < n; second++) {
               //需要和上一次枚举的数不相同
               if (second > first + 1 && nums[second] == nums[second -1]) {
                   continue;
                }
               //找a+b+c=0
               while (second < third && nums[second] + nums[third] > target) {
                   third--;
               }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
           }
       }
        return ans;
    }