目录
一：双数之和
1.题目：
2.思路解析
3.代码
二：三数之和
1.题目
2.思路解析
3，代码
三：四数字之和
1.题目
2.思路解析
3.代码
一：双数之和
1.题目：
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使他们的和正好是s，如果有多对数字的和是s，则输出一对即可
2.思路解析
这个题目要求检索数组中两个数字的和为s，那么就需要使用双指针去遍历这个数组，每遍历一次，就和s对比一下
暴力求解就是枚举法，时间复杂度太大了，这里不过多赘述
如果是稍微巧妙一点的解法，便是将left初始化放在数组最左边，right最右边，然后二者向着中间遍历，
一边遍历一边对left和right所指向的数字求和（sum），并且和目标值target对比，
如果比target小，那么就是小的数字（left）太小了，那么就需要left++，
如果比target大，那么就是大的数字太大了，就需要right--
3.代码
至于题目中的要求“如果有多对数字的和是s，则输出一对即可”，这句话的意思就是要“去重”，在STL中，我们可以直接使用容器“set”直接去重，至于如何手搓轮子，请向下看
二：三数之和
1.题目
2.思路解析
总而言之就是双指针的思维基础下又在上面套了一层循环
a.先将无需数组排列成有序数组
b. 双指针：cur自左向右遍历，cur对数组的遍历作为最外层的循环，本体中，我们的target=0
所以需要三个数字和为0，那么left和right所指向的数字的和必然是cur所指向的数字的相反数
由于是有序数组，具有单调性，如果cur>0,那么后面必然是正数，此情况便可以排除
c：去重操作：
left去重:left向右移动一格，如果和上一个数字相同，那么便skip
right去重：right向左移动一格，如果和上一个数字相同，那么skip
cur去重：cur向右走，每次向右都要注意越界（left<right）
d：cur++是最外层的循环。
图
3，代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int n = nums.size();
int cur = 0;
while(cur<n)
{
int left = cur + 1, right = n - 1;
int target = -nums[cur];
while (left < right)
{
int sum = nums[left] + nums[right];
if (nums[cur] > 0) break;
if (sum < target)
{left++;}
else if (sum > target)
{right--;}
else
{
ret.push_back({ nums[cur],nums[left],nums[right] });
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) { left++; }
while (left < right && nums[right] == nums[right + 1]) { right--; }
}
}
cur++;
while (cur < nums.size() && nums[cur] == nums[cur - 1]) { cur++; }
}
return ret;
}
};
总结：三数之和的大体思路就是
首先明确一点最后要转换成双指针
因为需要找到三个数字之和为target
所以先将cur固定住，再另外两个数字(双指针操作)和为target-cur
三：四数字之和
1.题目
. - 力扣（LeetCode）
2.思路解析
这个四数之和的思路不能说和三数之和类似，只能说是一摸一样的，不管几个数字，其核心思路都是最开始的双数之和
如果要将四数之和变成双指针双数之和思想，那么和三数之和一样，将双数之和外套两个循环
仍然是双指针遍历相加然后和target进行对比
3.代码
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();
int a=0;
while(a<n)
{
int b=a+1;
while(b<n)
{
long long aim=(long long)target-(long long)nums[a]-(long long)nums[b];
int left=b+1,right=n-1;
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<aim) {left++;}
else if(sum>aim) {right--;}
else
{
ret.push_back({nums[a],nums[b],nums[left],nums[right]});
left++; right--;
while(left<right&&nums[left]==nums[left-1]) {left++;}
while(left<right&&nums[right]==nums[right+1]) {right--;}
}
}
b++;
while(b<n&&nums[b]==nums[b-1]) {b++;}
}
a++;
while(a<n&&nums[a]==nums[a-1]) {a++;}
}
return ret;
}
};
