双指针算法：两数之和与三数之和

结束条件自然是左小于右，因为返回的是 vector，都没有找到的话返回空即可，时间复杂度是 O(N),没有新开空间，所以空间复杂度为 O(1)。

三数之和

题目解析

由题目可得，找三个数，其中这三个数相加等于 0，我们不妨将题目理解为，找一个数，该数 = 另外两数之和，是不是就感觉容易多了？不过是上文和为 s 的变种而已，我们只是需要将 S 变化一下即可。

以上是题目的最基本的要求，那么还有一个要求是，不允许出现重复的，这是和本文第一道题不同的要求，这点代表了我们要去重即可。

那么同样的，我们思考如何暴力解法？

暴力解法无非是将所有的三元组列出来，判断和是否为零，满足条件，我们可以将它丢进 set，用 set 本身的性质进行去重即可。

但是暴力解法的时间复杂度可就高了，三个数都要单独列出，也就是需要三个循环，时间复杂度为 O(N^3)，往往是通过不了的。

所以，我们进入到算法原理方面。

算法原理

我们同样的使用双指针算法，因为是双指针不是三指针，所以需要我们固定一个数，用来充当 target，有了第一个题目的经验，我们不妨排序一下，保证数组有序的同时有利于我们控制指针变量，排序之后对于我们去重的操作也会容易很多。

排序之后，固定好 target，然后进入到第二个循环，通过双指针算法，找两个数，使该三个数相加等于 0 即可。

那么指针移动分为两种情况，如果前面两个数相加>target，代表 right 大了，需要 right--，反之亦然，这是移动的情况。满足条件的话，添加进去就可以了。

那么最重要的点来了，我们如何进行去重操作呢？

判断的是 nums[left] == nums[left + 1] 是否相等即可，如果相等了，left 就++，right 同理，但是去重的不只有这两个数，还有一个数也需要去重，就是 nums[i]，如果 i 不去重，肯定是很导致很多重复的元素，毕竟都是会从头开始找的。

去重 i 的时候，需要控制 i 的移动，因为去重操作本身就会控制指针移动。

算法编写

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for(int i = nums.size() - 1; i > 1 && nums[i] >= 0;) {
            int target = nums[i];
            int left = 0, right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > (-target)) right--;
                else if(nums[left] + nums[right] < (-target)) left++;
                else {
                    ans.push_back({nums[left++], nums[right--], nums[i]});
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i--;
            while(i < nums.size() && nums[i] == nums[i + 1]) i--;
        }
        return ans;
    }
};

三个去重，一个排序，三个判断，最后返回即可。