Leetcode每日刷题之15.三数之和

1.题目解析

本次我们要做的题是15.三数之和 ，其题目大意就是找出数组中不重复的三元组，使其下标各不相同且和一定为0，需要注意的是这里的重复，代表的是只要数值重复就算重复，并不是只有下标重复才算重复

2.算法原理

具体我们用到的算法是"双指针"算法，首先创建一个二维数组存储符合要求的三元组，随后对原数组排序，然后定位第一个数为目标数，在剩余数据范围内的首尾固定两个指针，找出和为目标数倒数的二元组，然后返回即可。需要注意的是注意不能遗漏也不能重复，所以这里核心的要点还有去重和避免遗漏

避免遗漏：在找到一组二元组后不能直接退出循环，如果未到循环结束，就继续遍历找出符合目标的二元组

去重：注意这里需要在两个地方去重。

1.对于目标数去重：在固定目标数的时候如果下一次所要固定的目标数与上一次固定的目标数相同就直接寻找下一个目标数直到不重复为止

2.对于二元组去重：在双指针遍历的时候如果两个指针遍历到与上一次所指向数字相同的数字那么就相向移动，直到遇见不同的数字即可

3.代码展示

这里的代码还需要注意下标越界，所以时刻注意 left < right 的条件

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        //1.创建一个二维数组存储数据
        vector<vector<int>> vv;

        //2.对原数组排序
        sort(nums.begin(),nums.end());

        int len = nums.size();
        for(int i = 0;i < len;)
        {
            //简单优化
            if(nums[i] > 0)
            {
                break;
            }
            int left = i + 1;
            int right = len - 1;
            int target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target)
                {
                    right--;
                }
                else if(sum < target)
                {
                    left++;
                }
                else
                {
                    vv.push_back({nums[i],nums[left],nums[right]});
                    left++;
                    right--;
                    //去重二元组
                    while(left < right && nums[right] == nums[right + 1])
                    {
                        right--;
                    }
                    while(left < right && nums[left] == nums[left - 1])
                    {
                        left++;
                    }
                }
            }
            //去重目标数
            i++;
            while(i < len && nums[i] == nums[i - 1])
            {
                i++;
            }
        }
        return vv;
    }
};