双指针算法篇：两数之和 、三数之和

目录

LCR 179. 查找总价格为目标值的两个商品（两数之和）

解题思路

暴力解法：

 双指针算法：

15. 三数之和

解题思路：

18. 四数之和

LCR 179. 查找总价格为目标值的两个商品（两数之和）

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

也就是两数之和等于target

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

解题思路

暴力解法：

两数之和等于target

购物车内的商品价格按照升序记录于数组，说明是一个有序数组：
暴力解法：
先for循环确定第一个数，再内层嵌套for循环确定第二个数这里要注意第二个数从第一个数的后面开始，因为前面的已经被计算过。
但是这个解法会超时。

暴力解法代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;
        for(int i=0;i<price.size()-1;i++)
        {
            for(int j=i+1;j<price.size();j++)
            {
                if(price[i]+price[j]==target)
                {
                ret.push_back(price[i]),ret.push_back(price[j]);
                return ret;
                }
            }
        }
        return ret;
    }
};

 双指针算法：

我们来使用第二种双指针算法：
n=数组size()-1;
先置左右指针，left=0,right=n;
1、如果nums[left]+nums[right]>target
那么说明right指针与任意值相加都是大于target的，因为left是最小值，所以我们舍弃这个值，right--；
2、如过nums[left]+nums[right]<target
那么说明left与任意值相加都小于target，因为right已经是最大值，所以 我们舍弃这个值，left++；
3、相等则输出left和right；

双指针算法代码 

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0;
        int right=price.size()-1;
        while(left<right)
        {
            if(price[left]+price[right]>target)
            {
                right--;
            }
            else if(price[left]+price[right]<target)
            {
                left++;
            }
            else
            {
                return {price[left],price[right]};
            }
        }
        return {-1,-1};
    }
};

15. 三数之和

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

你返回所有和为 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] 。
注意，输出的顺序和三元组的顺序并不重要。

解题思路：

三数之和：
思路与二数之和的思路相似。
我们先对数组进行排序，这样有利于返回数组的去重工作，因为有序状态下，重复的三元组中的顺序是一样的。
我们依旧使用左右指针的方法，需要先确定一个值，在这里我们用i来表示，nums[i]来做第一个值，每次循环时，使用target=-nums[i]来记录，
int n=nums.size();
left为i+1，right为n-1;
这里需要注意一个小优化，当nums[i]>0时，因为 数组有序，三值相加必定大于0，绝对不符合条件。
找到nums[left]+nums[right]==target的时候就是符合条件的三元组。
调整左右指针的方法：
与两数之和相似
去重：
当调整完后，如果值与上一个值相同，那么结果也肯定是相同的，所以要跳过相同的值，同时也要注意i的去重。

代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int i=0;
        while(i<n-2)
        {
            if(nums[i]>0)
            break;
            int left=i+1;
            int right=n-1;
            int target=-nums[i];
            while(left<right)
            {
                if(nums[left]+nums[right]>target)
                {
                    right--;
                }
                else if(nums[left]+nums[right]<target)
                {
                    left++;
                }
                else
                {
                    ret.push_back({nums[left],nums[right],-target});
                    left++;
                    right--;
                    while(left<right&&nums[left]==nums[left-1]) left++;//去重
                    while(left<right&&nums[right]==nums[right+1]) right--;
                }
                
            }
            i++;
            while(i<n&&nums[i]==nums[i-1])
            i++;
        }
        return ret;
    }
};

 以上就是两数之和和三数之和的解题思路，至于后面的四数之和，思路也与上面一致 ，先排序，然后依次确定第一，第二，第三，第四个数，并注意去重。

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

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

示例 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]]

解题代码：

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