【算法|双指针系列No.8】leetcode18. 四数之和

今天药忘吃喽~ 2024-04-27 06:33 40阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。  
> ![在这里插入图片描述][7d5f5c0522df4548bdccccb6842f0211.png]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣算法分析
 *  3️⃣代码编写

## 1️⃣题目描述 ##

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

*  `0 <= a, b, c, d < n`
 *  `a、b、c 和 d 互不相同`
 *  `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\]\]

**注意：**

*  `1 <= nums.length <= 200`
 *  `-109 <= nums[i] <= 109`
 *  `-109 <= target <= 109`

## 2️⃣算法分析 ##

**解题思路依然是双指针和利用单调性，如下：**

*  在第一个指针i确定的情况下，设定`第二个指针j=i+1`，从i+1到n-1进行遍历。
 *  在第一个和第二个指针确定的情况下，设定`两个指针l=j+1和r=n-1`，分别表示左右两端的指针。对`l和r指针`进行迭代，判断`nums[l]+nums[r]`与目标值`target-nums[i]-nums[j]`的大小关系，如果小于目标值，则将l指针右移，如果大于目标值，则将r指针左移，如果等于目标值，则将结果加入ret数组，并继续移动l和r指针。
 *  在移动l和r指针的过程中，需要注意去重，即跳过重复元素（**此处为第一个需要去重的点**）。
 *  遍历完l和r指针之后，移动j指针，注意去重（**此处为第二个需要去重的点**）。
 *  遍历完j指针之后，移动i指针，同样需要注意去重（**此处为第三个需要去重的点**）。
 *  `最后返回ret即可`。

## 3️⃣代码编写 ##

class Solution {
        
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
            sort(nums.begin(),nums.end());
            int n = nums.size();
            vector<vector<int>> ret;
            for(int i = 0;i < n;)
            {
        
                int first = target - nums[i];
                for(int j = i + 1;j < n;)
                {
        
                    long long second = (long long)first - nums[j];
                    int l = j + 1, r = n - 1;
                    while(l < r)
                    {
        
                        if(nums[l] + nums[r] > second) r--;
                        else if(nums[l] + nums[r] < second) l++;
                        else
                        {
        
                            ret.push_back({
        nums[i],nums[j],nums[l],nums[r]});
                            l++,r--;
                            while(l < r && nums[l] == nums[l - 1]) l++;
                            while(l < r && nums[r] == nums[r + 1]) r--;
                        }
                    }
                    j++;
                    while(j < n && nums[j] == nums[j - 1]) j++;
                }
                i++;
                while(i < n && nums[i] == nums[i - 1]) i++;
            }
            return ret;
        }
    };

**最后就是通过啦！！！**

![在这里插入图片描述][e046deaecc004cea937d57ca99802c78.png]

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[7d5f5c0522df4548bdccccb6842f0211.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/32cb1a15c35640d2ac1cda1f580722a1.png
[e046deaecc004cea937d57ca99802c78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4ef1cd901fbf400fb01d8bcb90fe040f.png