双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动（3）
前言：本篇来到双指针算法介绍的最终篇，该文将通过三个同类型但难度逐渐累增的题目，再次强化对双指针算法的理解和运用。
相关题目及讲解
一. 两数之和
题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
题目分析：
1. 该题要求较为简单，只需要在数组中查找两个和为target的元素，并将他们储存在需要返回的数组中即可。
2. 需要注意找到任一一对即可返回，无需返回多种情况。
思路讲解：
解法一：暴力解法（会超时）
很容易想到采用两个for循环直接逐个遍历的方式，符合要求即可直接返回。
代码示例如下：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
for (int j = i + 1; j < n; j++) { // 第⼆层循环从 i 位置之后列举第⼆个数
if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值，说明我们已经找到结果了
return {nums[i], nums[j]};
}
}
return {-1, -1};
}
};解法二：对撞指针
基于解法一遍历思想的基础之上，我们对其通过减少遍历次数进行优化。
1. 首先对数组进行排序
2. 定义left=0，right=n-1，分别位于数组的左右两侧，代表最小和最大值。
3. 用sum表示nums[left]与nums[right]的和，与target比较。
如果sum>target，则此时和过大，应该让right--
如果sum<target，则此时和过小，应该让left++
如果sum=target，插入返回的数组中直接返回即可
代码实现：
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int n=price.size();
vector<int> ret;
int left=0,right=n-1;
while(left<right)
{
int sum=price[left]+price[right];
if(sum>target)
{
right--;
}
if(sum<target)
{
left++;
}
if(sum==target)
{
ret.push_back(price[left]);
ret.push_back(price[right]);
return ret;
}
}
return ret;
}
};二. 三数之和
题目链接：15. 三数之和 - 力扣（LeetCode）
题目分析：
1. 需要在一个数组内查找三个相加后和为0的元素
2. 这三个元素不能重复，但元素的值可以相同
3. 输出中不能包含内容相同的三元数组
思路讲解：
解法一： 暴力解法（会超时）
思路与两数之和大致相同，只是需要再嵌套一层for循环代表第三个数即可。
此时时间复杂度已经来到了恐怖的O(n^3)，基本上是一定会超时的。
解法二：对撞指针
1. 首先排序数组
2. 在求解两数之和时，我们就采取了对撞指针的方法，那么此时是三数之和，我们只需要固定一个数，在该数右侧的区间内使用对撞指针即可。
3. 使用for循环初始化一个i，那么i表示的就是我们需要固定的值，令left=i+1,right=n-1，重复两数之和的操作即可。只不过这次所求的target为-nums[i]。
4. 在查找到符合条件的元素时，我们将nums[i],nums[left],nums[right]插入要返回的数组中，并进行去重操作：
由于每一轮插入成功后，都会令left++，right--，此时要考虑以下几种情况进行去重：
1) 当nums[left]=nums[left-1]时，说明此处的left元素与上一个插入的相同，因此需要left++进行跳过。
2) 当nums[right]=nums[right+1]时，说明此处的right元素与上一个插入的相同，因此需要right--进行跳过。
注意：循环和去重操作均需满足条件left<right！！！
5. i的去重操作与上基本相同。
代码实现：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(),nums.end());//排序
int n=nums.size();//总元素的个数
for(int i=0;i<n;)
{
int target=-nums[i];
if(target<0)
{
break;
}//说明元素全部大于0，不存在满足的情况
int left=i+1,right=n-1;
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum>target)
{
right--;
}
else if(sum<target)
{
left++;
}
else
{
ret.push_back({nums[i],nums[left],nums[right]});
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. 四数之和 - 力扣（LeetCode）
题目分析：
1. 从数组内寻找4个加起来和为target的元素插入到需要返回的数组中
2. 元素不可以重复
3. 元素所代表的值可以重复
4. 需要返回所有情况
思路讲解：
1. 首先排序数组
2. 基于三数之和的思想，我们只需要固定一个数，在其右侧的区间进行三数之和的对撞指针和去重操作即可。
3. 需注意固定的这个数字在遍历的时候也需要去重。
代码实现：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());//排序
vector<vector<int>> ret;
int n=nums.size();
for(int i=0;i<n;)
{
for(int j=i+1;j<n;)
{
int left=j+1,right=n-1;
long long flag=(long long)target-nums[i]-nums[j];
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<flag)
{
left++;
}
else if(sum>flag)
{
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;
}
};小结：
对双指针算法的讲解就先告一段落啦，敬请期待下篇关于滑动窗口算法的介绍，欢迎各位佬前来支持斧正！！！
