【C++ leetcode】双指针（专题完结）

15. 三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目链接

. – 力扣（LeetCode）

画图 和 文字 分析

这道题和 两数之和等于一个值 大体思路是一样的，都是 排序 + 双指针思想

排完序后，我们定义三个指针，一个指向最后一个元素的位置，一个指向首元素的位置，另一个首元素的后一个位置

举例：

输入： [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

先固定 k不动

1. 如果三者指向的值相加为 0 ,则记录数据 ，再 j++ , k–
2. 如果三者指向的值 < 0 ，则 j++
3. 如果三者指向的值 > 0 ，则 k–

当 i >= j （结束里层循环）

再 i++ , j = i + 1 , k = n – 1

直到 i + 1 >= k (外层循环)

做到以上，只能说完成了完成了不漏掉每一种情况，但现在还有去重的关键一步

去重需要我们在前面的基础上做更改：

第一种情况：

走完上面的步骤 :

判断现在 j 所指的内容 和 j – 1 所指内容是否相同，直到不相同为止（这里需要一个循环，此时要么，j 指向一个不和之前相重复的数，要么越界）

判断 k 同理

上面是里层循环的去重，外层循环也可以去重

当结束里层循环，完成后面的步骤 ：

判断 i 所指向的内容 和 i – 1所指向的内容是否相同，直到不相同为止

注意:

去重的时候，因为循环的缘故，一定要防止越界

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> t;
        sort(nums.begin(),nums.end());
        int i = 0;
        while(i + 2 <= nums.size() - 1)
        {
            int j = i + 1;
            int k = nums.size() - 1;;
            while(j < k)
            {
                if(nums[i] + nums[j] + nums[k] > 0)
                {
                    k--;
                }
                else if(nums[i] + nums[j] + nums[k] < 0)
                {
                    j++;
                }
                else
                {
                    vector<int> x;
                    x.push_back(nums[i]);
                    x.push_back(nums[j]);
                    x.push_back(nums[k]);
                    t.push_back(x);
                    int n = nums[j];
                    int m = nums[k];
                    k--;
                    j++;
                    while(j < k && n == nums[j])
                    {
                        j++;
                    }
                    while(j < k && m == nums[k])
                    {
                        k--;
                    }
                }
            }
            int h = nums[i];
            i++;
            while(i + 2 <= nums.size() - 1 && h == nums[i])
            {
                i++;
            }
        }
        
        return t;
    }
};

18 . 四数之和

题目

给你一个由 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

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

题目链接

. – 力扣（LeetCode）

画图 和 文字 分析

在 leetcode 15. 三数之和 基础之上做出的改变

思想：排序 + 双指针思想

定义四个指针，三个指针分别指向前三个元素的位置，第四个指针指向最后一个元素的位置

举例：

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

输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

后面的三个指针和之前的做法一模一样，第一个指针在里层所有循环结束后++

再判断现在 a 所指向的元素和 a – 1 所指向的元素是否相同

直到 a + 2 >= d (外层循环结束)

注意：

1. 注意越界情况
2. 判断四数之和是否得到一个值，这里容易由于数据过大发生整型溢出现象，可以改成 longlong 类型 或者针对处理这一可能

代码

class Solution {public:    bool iscompare(int &a,int &b,int &c,int &d,int &target)    {         if(target < 0 && (a >= 0 && b >= 0 && c >= 0 && d >= 0))         {            return false;         }         else if(target > 0 && (a <= 0 && b <= 0 && c <= 0 && d <= 0))         {            return false;         }         else if(target == 0 && ((a > 0 && b > 0 && c > 0 && d > 0) || (a > 0 && b > 0 && c > 0 && d > 0)))         {            return false;         }         else         {            return true;         }    }    vector<vector<int>> fourSum(vector<int>& nums, int target)     {        vector<vector<int>> s;        int n = nums.size() - 1;        sort(nums.begin(),nums.end());        int a = 0;        while(a + 2 < n)        {            int b = a + 1;            while(b + 1 < n)            {                                int  c = b + 1;                int  d = n;                while(c < d)                {                    if(!iscompare(nums[a],nums[b],nums[c],nums[d],target))                    {                        break;                    }                    if(nums[a] + nums[b]  > target - nums[c] - nums[d] )                    {                        d--;                    }                    else if(nums[a] + nums[b]  < target - nums[c] - nums[d] )                    {                        c++;                    }                    else                    {                        vector<int> t;                        t.push_back(nums[a]);                        t.push_back(nums[b]);                        t.push_back(nums[c]);                        t.push_back(nums[d]);                        s.push_back(t);                        int s1 = nums[c];                        int s2 = nums[d];                        d--;                        c++;                        while(c < d && nums[c] == s1)                        {                            c++;                        }                        while(c < d && nums[d] == s1)                        {                            d--;                        }                    }                }                int s3 = nums[b];                b++;                while(b + 1 < n && nums[b] == s3)                {                   b++;                }            }            int s4 = nums[a];            a++;            while(a + 2 < n && nums[a] == s4)            {                a++;            }        }        return s;    }};