【优选算法】详解target类求和问题（附总结）

1.两数求和

题目：

算法思路：

代码：

2.！！！三数之和

题目

算法思路：

代码：

3.四数字和

题目：

算法思路：

代码：

总结&易错点：

1.两数求和

剑指Offer57.和为s的两个数字

题目：

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 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]

算法思路：

双指针-对撞指针：注意到本题是升序的数组，因此可以⽤「对撞指针」优化时间复杂度。

算法流程（附带算法分析，为什么可以使⽤对撞指针）

a. 初始化left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下标）

b. 当left < right 的时候，⼀直循环

i. 当nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；

ii. 当nums[left] + nums[right] < target 时：

对于nums[left] ⽽⾔，此时nums[right] 相当于是nums[left] 能碰到的最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让left++ ，去⽐较下⼀组数据；
那对nums[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， nums[right] 还可以选择⽐nums[left] ⼤的值继续努⼒达到⽬标值，因此right 指针我们按兵不动；

iii. 当nums[left] + nums[right] > target 时，同理我们可以舍去 nums[right] （最⼩的数都满⾜不了你，你也没救了）。让right-- ，继续⽐较下⼀组数据，⽽left 指针不变（因为他还是可以去匹配⽐nums[right] 更⼩的数的）。

代码：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//left++ right-- num+num=targetint n=nums.size();int left=0,right=n-1;while(left!=right){int sum=nums[left]+nums[right];if(sum<target)left++;else if(sum>target)right--;elsereturn {nums[left],nums[right]};//vector用大括号}return {-1,-1};//注意返回值的设定}
};

2.！！！三数之和

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] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0

算法思路：

（排序+双指针）

本题与两数之和类似，是⾮常经典的⾯试题。与两数之和稍微不同的是，题⽬中要求找到所有「不重复」的三元组。

那我们可以利⽤在两数之和那⾥⽤的双指针思想，来对我们的暴⼒枚举做优化：

i. 先排序；

ii. 然后固定⼀个数a ：

iii. 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于-a 即可。但是要注意的是，这道题⾥⾯需要有「去重」操作~

i. 找到⼀个结果之后， left 和right 指针要「跳过重复」的元素；
ii. 当使⽤完⼀次双指针算法之后，固定的a 也要「跳过重复」的元素。

代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());//排序// 设置一个ret来接收返回类型vector<vector<int>> ret;int n = nums.size();for (int c = 0; c <= n - 3;) {// 优化if (nums[c] > 0)break;int x = -nums[c];                // 是数字不是下标int left = c + 1, right = n - 1; // 是变换的，要在循环体里面定义while (left < right) {int sum = nums[left] + nums[right];if (sum < x)left++;else if (sum > x)right--;else {ret.push_back({ nums[c], nums[left], nums[right] });left++;right--;// 去重,while重新加一个条件运行while (left < right && nums[left] == nums[left - 1])left++; // 如果相等，就++跳过while (right > left && nums[right] == nums[right + 1])//不要糊涂，要清楚的列出伪代码！！right--;}}// 去重ic++;while (c <= n - 3 && nums[c] == nums[c - 1])c++; // 在循环内如果还出现这个相等条件，就再++// 在哪一步判断完之后需要执行去重，就在后面加上出现条件的处理}return ret; // 对于链表数组的理解}
};

3.四数字和

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

算法思路：

a. 依次固定⼀个数a ；

b. 在这个数a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于target - a 即可。

代码：

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; )//固定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];//可能很大，所以用long long来设置while(left<right){int sum=nums[left]+nums[right];//sum每次都要重新刷新if(sum<aim) left++;else if(sum>aim) right--;else{ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//去重1while(left<right&&nums[left]==nums[left-1])left++;//和前一个相等，就跳过while(left<right&&nums[right]==nums[right+1])right--;//和后一个相等就跳过，不要糊涂}}//去重2j++;while(j<n&&nums[j]==nums[j-1])j++;}i++;//每次到了下一个，就要判断一下，是否重复，重复就要跳过while(i<n&&nums[i]==nums[i-1])i++;}return ret;}
};