LeetCode热题 15.三数之和（双指针）

题目

思路：

最简单的最暴力的想法就是三重循环便利所有可能的三元组，检查他们的和是否为零，并去除重复的组合。这种的时间复杂度是0(n^3)。
这时候我们可以想到 对于 a + b + c = 0求不重复的三元组，等价于 固定一个 a，求 b + c = -a 的不重复的 二元组。
我们可以排一下序，固定a，从0开始往右走，然后对于每个a，b和c双指针，分别从 a + 1 往右和 n - 1 往左走，每次判断一下：

• 如果满足 b + c = -a 就记录一下，然后两个指针分别往右 往左移动一下，这里注意的是去重。 在移动一下之前，要判断是否下一个和当前相等，往前一直走。
• 如果 b + c < -a，那我们就把小的 b （因为是递增的）往右挪一下
• 如果 b + c > -a，那我们就把大的 c往左挪一下。
  具体代码：

 vector<vector<int>> ans; //  结果
        int len = nums.size();  // 长度
        if (len < 3) return ans;  // 优化  如果就没有3个，直接返回空  无解

        sort(nums.begin(), nums.end());  //  排序

        for (int i = 0; i < len - 2; i ++ ){  // 固定三元组最小那一个 num[i] 也就是 a
            if (nums[i] > 0) break;  // 最小的都大于 0 了，那不可能合为0了，直接无解

            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的 a

            int left = i + 1, right = len - 1;  // 双指针
            int temp = -nums[i];  //  需要找的两数和

            while (left < right){
                int sum = nums[left] + nums[right];
                if (sum == temp){  //  找到解
                    ans.push_back({nums[i], nums[left], nums[right]});

					//  跳过重复的 left  和 right
                    while(left < right && nums[left] == nums[left + 1]) left ++;
                    while(left < right && nums[right] == nums[right - 1]) right --;

					//  这里不要忘记移动一下，前面循环结束nums[left]还是上面记录过的解的那个值，需要再移动一下  到下一个不同的值
                    left ++;
                    right --;  
                } else if (sum < temp) left ++;  //  和小了，让左指针右移
                else right --;  //  和大了，让右指针左移
            }
        }

        return ans;