【算法——双指针】LeetCode 15 三数之和

题目描述：

解题思路：双指针

        首先，按升序对数组进行排序。然后，我们可以用如下步骤求解：

        初始化一个空的结果集result，用于存储找到的和为0的三元组。

        遍历整个数组，直到倒数第三个元素（因为我们需要的是一个三元组）。对于每个元素，用两个指针（一个左指针L和一个右指针R）找到所有的和为0的三元组。

1. 初始化左指针L，将其设置为当前元素的下一个元素；初始化右指针R，将其设置为数组最后一个元素。
2. 如果当前元素与前一个元素（如果存在）相同，我们只需跳过当前元素，因为我们需要避免重复的解，并继续处理下一个元素。
3. 对于当前元素nums[i]，检查nums[i] + nums[L] + nums[R]的和：
   1. 如果和小于0，增加左指针L；
   2. 如果和大于0，减小右指针R；
   3. 如果和等于0，将这个三元组[nums[i], nums[L], nums[R]]添加到结果集result中，并同时移动左指针L和右指针R，直到遇到与当前元素不相等的元素（避免重复解）。
   4. 最后，返回结果集result。

        这个方法的时间复杂度为O(n^2)，这是因为需要对整个数组进行遍历，而每个元素又可能需要遍历一次。

        在编写实现时，请确保在处理左指针和右指针时移动到不相等的元素，以避免重复的解。

代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector& nums) 
    {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 1; i++)
        {  
            if(nums[i] > 0)
                return result;    //数组递增
            if(i > 0 && nums[i] == nums[i - 1])
            {
                continue;    //对a去重，如果i=1与i=0对应的元素相同，那么跳过下面的所有操作，left,right不需要考虑了。
            }
            //a满足去重，再来确定left,right以及去除问题。
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right)
            {
                //当left==right时，b，c为同一个数，不符合要求。
                if(nums[i] + nums[left] + nums[right] < 0) 
                    left++;
                else if(nums[i] + nums[left] + nums[right] > 0) 
                    right--;
                else
                {
                    vector<int> v = {nums[i], nums[left], nums[right]};
                    result.push_back(v);
                    //下面考虑left，right的移动情况。
                    while (right > left && nums[right] == nums[right - 1])
                        right--;
                    //再次加上right>left的原因是：进入上面的循环时是复合right>left的，但是
                    //可能在循环中left与right发生改变。
                    while (right > left && nums[left] == nums[left + 1]) 
                        left++;
                    /*
                    为什么是while?举个例子
                    [0 -1 -1 -1 -1 -1 1 1 1 1 1 1 ]
                    因为当i= 0时，left与right就已经收集到了正确的结果
                    此时应该持续地移动left 与 right，一次是不够。
                    */
                   
                    left++;
                    right--;
 
                    //是为了在找到一个有效的三元组后，将left和right分别向前和向后移动一位，以便在后续的循环中继续寻找其他可能的三元组。这样可以确保所有的有效三元组都被找到。
                }
            }
        }           
    return result;   
    }
};

结果：