指尖的无声告白，算法里的隐约温柔

1. 三数之和

题目传送门

1. 题目说明

给定一个整数数组 nums，判断数组中是否存在三个元素 nums[i], nums[j], nums[k]，使得它们的和为 0，返回所有符合条件且不重复的三元组。要求：

• 三元组 [nums[i], nums[j], nums[k]] 满足 i != j != k，同时 nums[i] + nums[j] + nums[k] == 0。
• 输出结果中不包含重复的三元组。

示例 1

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是[-1,0,1]和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2

输入：nums = [0, 1, 1]
输出：[]

示例 3

输入：nums = [0, 0, 0]
输出：[[0, 0, 0]]

1.2 题目分析

题目要求nums[i] + nums[j] + nums[k] == 0。那么我们就得在数组中找到这对应的三个数
解法一： 暴力枚举法：将所有的可能性都表示出来，然后利用set进行去重操作
解法二： 使用排序+双指针就能进行解决了
那么对于这两种方法的话我们肯定是选择这个第二种方法的，因为效率高
我来具体讲下我的思路：
我们将排序好的数组的第一个数字进行一个固定的操作，然后从1到n-1这个下标范围进行满足两数之和为0的条件的数字的寻找
然后我们在这个区间之内我们就能利用双指针进行满足条件的数字的寻找了
总结：

• 1.先排序

• 2.固定一个数a（我们固定的数小于等于0就行了，不需要去固定大于0的，如果固定的是大于0的数字的话我们是不能在这个数后面的区间之内找到负数的，所以我们固定a的时候我们只需要在负数和0之间进行固定的操作，当a大于0之后我们就不要进行考虑统计了）

• 3.在该数后面的区间内利用‘双指针算法’，快速找到两个的和等于a就行了

处理细节问题：

• 1.去重（不借助set进行去重的操作）

  找到一种结果之后，left(right要跳过重复元素)

  当使用完一次双指针算法之后，i也需要跳过重复元素

  避免越界（如果数组中全是0的话，i跳过重复元素，可能会存在越界的情况）

left<right这个就会保证不越界了

• 2.不漏（将所有情况都找到）

  找到一种结果之后，不要停下来，缩小区间，继续寻找

1.3 代码部分

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>>ret;//用ret来记录我们最终的结果
        //1.排序
        sort(nums.begin(),nums.end());
        
        //2.利用双指针进行问题的解决
        int n=nums.size();
        for(int i=0;i<n;)//固定数a
        {
            if(nums[i]>0)//我们固定的数只选择小于0或者等于0的数字，不选择正数，这个是个小优化
            {
                break;
            }
            //我们在固定数i后面的区间继续双指针的操作的
            int left=i+1,right=n-1,target=-nums[i];//我们在后面的区间只需要将target寻找到，看看是哪两个指针之和
            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]});//将我们最后得到的三元组的答案存放在ret中
                    left++,right--;//这个就是保证没有情况漏掉，进一步缩小区间

                    //去重left和right
                    while(left<right && nums[left]==nums[left-1])//如果下一个数字和前一个数字是相等的话我们一直进行加加的操作，直到我们的这个数和之前的数不相等了
                    {
                        //但是如果我们碰到了特殊情况的话，就是一组数字全是0，然后我们这个Left就是有可能的造成越界的情况了
                        //所以我们在移动的时候我们的left要小于right
                        //所以我们要在这个循环中加上一个条件，就是左指针小于右指针
                        left++;
                    }

                    //处理完left的重复和越界问题之后我们还要处理这个right的重复和越界问题
                    while(left<right && nums[right]==nums[right+1])//nums[right]==nums[right+1]这个就是重复元素
                    //重复的话就进行这个right--的操作
                    {
                        right--;
                    }
                    //通过这两个while循环我们就能实现这个去重的操作了
                }
            }
     //当我们的内部循环第一个while循环结束后我们的第一个i所涉及到的三元组就全部找到了，那么我们接下来就对i进行去重操作
            i++; 
            while(i<n && nums[i]==nums[i-1])
            {
                i++;
            }//加到nums[i]和前面的数不相同，但是这个也存在越界的情况
            //我们在这个for循环中我们的第三个条件我们可以不写i++，可以空着，因为我们这里已经存在i++的操作了
        }
        return ret;

        
        

    }
};
//时间复杂度是n^2级别的，空间发复杂度logn

1.3 代码分析

我们先用sort进行一个排序的操作

然后通过for循环固定住这个a，并且这个a不能是正数，这个时间个优化，只能是负数和0

我们在固定的那个数的后面那个数开始，直到最后一个数直接的区域通过双指针来获取我们固定的数的相反数，这个相反数就是两个指针之和，

这个target就是我们固定的那个数字的相反数了

然后我们进行一个while进行循环的操作

对于两数之和的话我们存在三种情况，如果算出来的数大于我们要找的target的值的话，我们就将right–

相反就是left++

还有一种情况就是我们找到了

通过这两个代码我们将符合条件的答案存储在这个ret中

然后我们进行缩小区域的操作继续进行寻找对应的数字

left++和right--进行区域的缩小操作

然后我们最后进行两个指针指向的数字的去重操作

对于left来说的话就是++后指向的数字和前一个数字是不是相等的

对于right来说的话就是–后的数字是不是和原先的数字是不是相等的话

如果是相等的话分别执行这个left++和right--,直到我们找到了这个不重复的数字

但是我们需要在这两个while循环的开头加上一个条件，就是left<right，保证两个指针不越界操作

处理完指针的越界操作之后

我们对i的去重进行一个操作

我们在for循环中就不需要写i++这个条件了，我们在这里就进行了，直到我们的i不是重复的数字

2. 四数之和

题目传送门

2.1 题目说明

给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件的不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

1. \( 0 <= a, b, c, d < n \)
2. \( a, b, c, d \) 互不相同
3. \( nums[a] + nums[b] + nums[c] + nums[d] == target \)

你可以按 任意顺序 返回答案。

示例 1

输入：nums = [1, 0, -1, 0, -2, 2], target = 0
输出：[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

示例 2

输入：nums = [2, 2, 2, 2, 2], target = 8
输出：[[2, 2, 2, 2]]

2.2 题目分析

解法一：
排序+暴力枚举+利用set去重
将所有的可能性列出来
解法二：
排序+双指针
我们在这个数组进行元素的固定，从第一个元素开始，然后我们后面的区间利用求三数之和的方法求的目标值

下面讲讲我的思路：

1.依次固定一个数a;

2.在a后面的区间内利用我们在三数之和的思想找到三个数，使这三个数的和等于target-a就行了

三数之和：

1.依次固定一个数b

2.在b后面的区间内利用双指针找到两个数，使这两个数的和等于target-a-b就行了

细节问题：

1.不重

2.不漏（找到一个结果的时候我们缩小区间继续进行寻找）

2.3 代码部分

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>>ret;//存放结果的数组
        //1.排序
        sort(nums.begin(),nums.end());

        //利用双指针解决问题
        int n=nums.size();
        for(int i =0;i<n;)//固定数a
        {
            //利用三数之和
            for(int j=i+1;j<n;)//固定数b
            {
                //利用双指针
                int left=j+1,right=n-1;
                long long aim=(long long)target-nums[i]-nums[j];//这个就是我们通过双指针要找到的两数之和
                while(left<right)//
                {
                    int sum=nums[left]+nums[right];
                    if(sum<aim) left++;
                    else if(sum>aim) right--;
                    else
                    {
                        ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//固定的a和b以及left和right指向的值
                    //找到一种结果之后我们进行缩小区间的操作继续进行寻找符合条件的数,我们在将结果存放到ret的时候进行left++,right--
                        //去重一：left和right要跳过和之前相同的元素
                        while(left<right && nums[left]==nums[left-1]) left++;
                        
                        //相等的话我们就进行跳过的操作，并且我们保证不越界 
                        while(left<right && nums[right]==nums[right+1]) right--;
                    }

                }

                //去重二：现在我们对b进行去重的操作
                j++;
                while(j<n && nums[j]==nums[j-1]) j++;//保证不越界并且这个++后的数和之前的数是不相等的，如果相等的话就一直进行++操作，而且我们最上面的for循环中就不需要写j++了，因为我们这里写了

            }
            //去重三：
            i++;
            while(i<n && nums[i]==nums[i-1]) i++;
            //同时我们上面的for循环也是不同进行i++的
        }
        return ret;
    }
};

2.4 代码解析

我们先利用vector创建一个数组容器（还没学到，说错了勿喷）
然后我们利用sort进行排序的操作
然后我们计算这个数组的大小
然后我们就可以利用双指针进行后面的操作了
我们利用一个for循环固定住数a
然后在循环里面我们利用我们之前学的三数之和的知识，
我们再使用一个for循环固定住数b，在这个循环里面我们利用双指针找到想要的两数之和
我们先定义left和right
我们在这个循环里面需要找到的两数之和的大小是目标值-a-b的大小
那么这个两数之和就是我们两个指针对应的数据了
我们先创建变量将这个我们需要找的值进行保存，然后我们再通过while循环进行遍历的操作，遍历的条件一定要是left<right，保证不能越界了
我们在循环里面再计算每次的左右指针下标之和sum 然后让sum和我们的目标值aim进行比较，然后再决定移动我们的哪个指针
大于小于的情况不说了，我们就说下等于的情况
当我们找到一种结果之后，我们还要继续往后面进行寻找，但是不能和当次的结果重复了，所以我们要进行去重的操作，我们在去重之前先将这个数据push_back到vector容器里面去存着
然后我们就可以开始去重的操作了
还是while循环，这个是对指针进行去重

然后对我们固定的b进行去重

然后对a进行去重

最后将值进行返回就行了
所以我们在这里是有三次去重的操作的
而且都很重要