优先算法 —— 双指针系列 - 三数之和

1. 三数之和

题目链接：

  

15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/

2. 题目解析

由题可以得出：三个数不能选择重复位置的下标，同时还要满足三数相加之和为0，并且不能返回重复的三元组合

  

结合示例1来理解：

  

  

我们可以这样选择：

  

  

注意：

  

3. 算法原理

解法1：暴力枚举

  

排序 + 暴力枚举 + 使用set进行去重  

我们可以先进行排序，这样我们枚举之后就会发现如果有相同的那么枚举出来的值是一样的

   

然后再使用set的特性进行去重

  

解法2：双指针算法

 排序 + 双指针

 

我们在暴力枚举的基础上进行优化，我们进行了排序，那么数组就变成了有序的，如果是有序的数组，那么我们一般使用 二分 或者 双指针 来解决，一般能够使用双指针来解决问题就不要使用二分

  

     

  

当a>0的时候就不需要考虑了  

  

当我们进行去重操作的时候，当数组是下面这种情况的话，我们的指针是有可能越界的

  

  

  

4. 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;//记录最终结果

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

        //固定完一个数之后使用双指针
        int n=nums.size();
        for(int i=0;i<n;)//固定数a
        {
            if(nums[i]>0) break;

            //target=-nums[i]目标值的相反数
            int left=i+1,right=n-1,target=-nums[i];
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum>target) right--;
                else if(sum<target) left++;
                else{
                    ret.push_back({nums[i],nums[left],nums[right]});
                    left++;
                    right--;

                    //进行l和r的去重操作
                    while(left<right && nums[left] == nums[left-1]) left++;
                    while(left<right && nums[right] == nums[right+1]) right--;
                }
            }
            //进行i的去重
            i++;//将for循环的i++放到这里
            while(i<n && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};

未完待续~