两数之和 ？ 三数之和？ 四数之和？ 统统搞定
🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一
前言
声明：题目来源于： 力扣
目录
- 前言
- 一、查找总价格为目标值的两个商品
- (1) 题目描述
- 示例
- (2)解题思路
- (3)代码展示:
- 二、三数之和
- (1) 题目描述
- 示例
- (2)解题思路
- (3)代码展示:
- 三、四数之和
- (1) 题目描述
- 示例：
- (2)解题思路
- (3)代码展示:
一、查找总价格为目标值的两个商品
题目链接：传送门
(1) 题目描述
购物车内的商品价格按照升序记录于数组 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]
(2)解题思路
- 定义双指针，
left指向最开始的元素，right指向最后一个元素。
- 如果
left+right>target
则我们将右指针向前移动，因为数据是有序的，所以移动右指针，left+right会减小。
- 如果
left+right<target（如上图） 则我们将左指针向前移动，因为数据是有序的，所以移动左指针，left+right会增大。 - 循环
2、3操作，直到找到left+right=target。 - 返回
left和right
(3)代码展示:
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left=0,right=price.size()-1;
vector<int> v(2);
while(left<right){
//如果left+right>target
if(price[left]+price[right]>target){
right--;
}如果left+right<target
else if(price[left]+price[right]<target){
left++;
}
else{ //表明//如果left+right=target，可以返回了
v[0]=price[left];
v[1]=price[right];
break;
}
}
return v;
}
};二、三数之和
题目链接：传送门
(1) 题目描述
给你一个整数数组 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 。
(2)解题思路
- 为了让我们更好的寻找数，排序是有利于提高我们的查找效率的。
- 要找到3个数的和为0，我们只需要固定一个数（end），然后找到两个数的和为-end即可。
- 初始化end指针，使其指向最后一个元素 寻找两个数的和为-end （1）初始化left使其指向第一个元素。 （2）初始化right，使其指向end的前一个元素。 4 .看到这里，应该不难知道，如何寻找寻找两个数的和为-end ，这不就是第一道题的要求吗？
- 如果left>right,表明end为前面的所有可能都已经统计过了，end往前移动一步，继续2、3步骤。
注意:
每次移动left和right包括end的时候，由于我们不能出现互不相同的三元组，所以我们需要跳过相同的元素。
(3)代码展示:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> vv1;
sort(nums.begin(), nums.end()); //先对数据进行排序
int end = nums.size() - 1; //end从最后一个元素开始查起
while (end >= 2) {
int right = end - 1;
int left = 0;
//找两个数
while (left < right) {
if ((nums[left] + nums[right]) == -nums[end]) {//找到以后
vector<int> v1 = { nums[left],nums[right],nums[end] };
vv1.push_back(v1);
left++, right--;
//都要跳过重复元素
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
if ((nums[left] + nums[right]) > -nums[end]) right--;
else if ((nums[left] + nums[right]) < -nums[end])left++;
}
//end也要跳过重复元素
end--;
while (end - 1 > 0 && nums[end] == nums[end + 1]) end--;
}
return vv1;
}
};三、四数之和
题目链接：传送门
(1) 题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同 （牛牛提醒一下，这里abcd是下标，而不是数组中的值）
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)解题思路
牛牛讲不动了，相信大家可以自己写出来的。
如果直接写第四题，我们可能无法下手，但是有了前两个的铺垫，现在写应该不算太困难了。
秘诀： 四数之和转化为三数之和。 三数之和转化为两数之和。
(3)代码展示:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> vv1;
sort(nums.begin(), nums.end());
int d = nums.size() - 1;
while (d >= 3) {
int c=d-1;
//找三个数
while(c>=2){
int a=0,b=c-1;
//找两个数
while (a < b) {
//找到以后
if (((long long )nums[a] + nums[b]+nums[c]+nums[d]) == (long long)target) {
vector<int> v1 = { nums[a],nums[b],nums[c],nums[d] };
vv1.push_back(v1);
a++, b--;
while (a < b && nums[a] == nums[a - 1]) a++;
while (a < b && nums[b] == nums[b + 1]) b--;
}
if ((long long )(nums[a] + nums[b]) > (long long)target-nums[d]-nums[c]) b--;
else if ((long long )(nums[a] + nums[b]) < (long long )target-nums[d]-nums[c])a++;
}
c--;
while (c > 0 && nums[c] == nums[c + 1]) c--;
}
d--;
while (d > 0 && nums[d] == nums[d + 1]) d--;
}
return vv1;
}
};好了，今天的算法题就到这里了，我们下次见！
腾讯云开发者
