1、两数之和；15、三数之和；18、四数之和
1、四数之和
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
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
2）分析
? 最直观的思路是使用四重循环枚举所有的四元组，将找到的所有满足条件的四元组去重之后返回。直接暴力枚举时间复杂度为O( n 4 n^4 n4)，去重的过程复杂度也很高。可以在枚举之前对数组进行排序，保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不多次枚举到相同的元素。此时，枚举时间复杂度为O( n 4 n^4 n4)，不需要去重。由于数组已经被排序，因此可以在第三重循环中使用双指针而省去第四重循环，此时枚举时间复杂度为O( n 3 n^3 n3)。
具体实现时，还可以进行一些剪枝操作：
- 在确定第一个数之后，如果
nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target，说明此时剩下的三个数无论取什么值，四数之和一定大于target，退出第一重循环； - 在确定第一个数之后，如果
nums[i]+nums[n?3]+nums[n?2]+nums[n?1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于target，第一重循环直接进入下一轮，枚举nums[i+1]； - 在确定前两个数之后，如果
nums[i]+nums[j]+nums[j+1]+nums[j+2]>target，说明此时剩下的两个数无论取什么值，四数之和一定大于target，退出第二重循环； - 在确定前两个数之后，如果
nums[i]+nums[j]+nums[n?2]+nums[n?1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于target，第二重循环直接进入下一轮，枚举nums[j+1]。
3）C++代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int lengthNum=nums.size();
//当n小于4时，直接返回空结果；
if(lengthNum<4)
return res;
//排序
sort(nums.begin(),nums.end());
//最小角四个数之和大于，或者最大四个数之和小于，直接发返回空结果
if((long)nums[0]+nums[1]+nums[2]+nums[3]>target)
return res;
if((long)nums[lengthNum-1]+nums[lengthNum-2]+nums[lengthNum-3]+nums[lengthNum-4]<target)
return res;
//双重循环+双指针
//选择第一个数
for(int i=0;i<lengthNum-3;i++){
//与前一个数相同，直接跳过
if(i>0&&nums[i]==nums[i-1])
continue;
//判断当前位置开始四个数之和以及与最后三个数之和与target的关系
if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)
break;
if((long)nums[i]+nums[lengthNum-1]+nums[lengthNum-2]+nums[lengthNum-3]<target)
continue;
//选择第二个数
for(int j=i+1;j<lengthNum-2;j++){
//与第一个数相同的三个剪枝条件
if(j>i+1&&nums[j]==nums[j-1])
continue;
if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)
break;
if((long)nums[i]+nums[j]+nums[lengthNum-1]+nums[lengthNum-2]<target)
continue;
//使用双指针选择第三个和第四个数，达到少使用一重循环的目的
int left=j+1;
int right=lengthNum-1;
while(left<right){
long sum=nums[i]+nums[j]+nums[left]+nums[right];
if(sum==target){
res.push_back({nums[i],nums[j],nums[left],nums[right]});
while(left<right&&nums[left]==nums[left+1])
left++;
left++;
while(left<right&&nums[right]==nums[right-1])
right--;
right--;
}
else if(sum>target)
right--;
else
left++;
}
}
}
return res;
}
};
2、三数之和
1）题目描述
? 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
2）分析
? 这一题和 四数之和 几乎一样，只需要两重循环+双指针即可，思路与 四数之和 完全一样。
3）C++代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int lengthNum=nums.size();
if(lengthNum<3){
return res;
}
sort(nums.begin(),nums.end());
if((long)nums[0]+nums[1]+nums[2]>0)
return res;
if((long)nums[lengthNum-1]+nums[lengthNum-2]+nums[lengthNum-3]<0)
return res;
for(int i=0;i<lengthNum-2;i++){
if(i>0&&nums[i-1]==nums[i])
continue;
if((long)nums[i]+nums[i+1]+nums[i+2]>0)
break;
if((long)nums[i]+nums[lengthNum-1]+nums[lengthNum-2]<0)
continue;
int left=i+1;
int right=lengthNum-1;
while(left<right){
long sum=nums[i]+nums[left]+nums[right];
if(!sum){
res.push_back({nums[i],nums[left],nums[right]});
while(left<right&&nums[left]==nums[left+1])
left++;
left++;
while(left<right&&nums[right]==nums[right-1])
right--;
right--;
}
else if(sum>0){
right--;
}
else{
left++;
}
}
}
return res;
}
};
3、两数之和
1）题目描述
? 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？
2）分析
? 本题要求返回数组下标，因此无法使用 四数之和 的思路了。不想动脑子了，直接暴力枚举，时间复杂度比较差。
3）C++代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> resIndex;
int flag=0;
for(int i=0;i<nums.size()-1;i++)
{
resIndex.push_back(i);
for(int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
{
resIndex.push_back(j);
flag++;
}
}
if(!flag)
{
resIndex.clear();
}
else
{
break;
}
}
return resIndex;
}
};
