【算法】——双指针（上）
目录
编辑
编辑
一、前言
二、正文
1.算法介绍
2.算法优点
3.具体案例
3.1 两数之和
3.1.1题目解析
3.1.2 算法原理
3.1.3 具体代码
3.2 三数之和
3.2.1题目解析
3.2.2算法原理
3.2.3具体代码
3.3 四数之和
3.3.1题目解析
3.3.2算法原理
3.3.3具体代码
三、结语
一、前言
在本文会为大家带来算法中有关双指针的讲解
二、正文
1.算法介绍
什么是双指针？
从字面上来看是不是就是利用两个指针来进行题目的解答?但是首先我们要明确的一点是虽然这个算法的名称叫做双指针，但还是其在实际操作的时候并不一定是实例化出两个指针在进行操作，有可能是数组的下标，又或者是根据我们的想象定义出来的两个变量。所以这里的“指针”实际是非常灵活的，本质是一种变量，可以是指针，也可以是数组下标。
2.算法优点
双指针有什么优点？
既然双指针本质上是一种变量，无非数量为两个罢了，为啥会被列入算法之中？笔者认为重要的通过这个双指针能够帮助我们简化一些冗余的步骤，从而提高算法效率。对于双指针这个算法，往往应用于一个封闭，固定的场景，比如数组，链表等，一般而言其长度是不会变化的。因此在这种场景下，当我们为了去满足需求时，往往会考虑暴力求解的方法，因为在这个场景下，所有的可能性是唯一的，我们只需要嵌套多层嵌套去穷举，与所求进行比对便可以拿到我们想要的结果 。
但是当穷举数据过多，未免时间复杂度就会过大，这时候通过双指针的方法我们就能够将其中一些不必要的穷举省去，达到降低复杂度的效果。原本为O(N)的穷举，可能只需要O(1)就可以解决，即降低一层。
3.具体案例
那么在实际应用中，我们到底是如何通过双指针来达到降低时间复杂度的效果呢？下面我们就来通过几个案例来看看。
注：以下题目的解法相比于暴力穷举，双指针可能并不是唯一的优化算法，但是限于本文，于是采取双指针的解法。
3.1 两数之和
1. 两数之和 - 力扣（LeetCode）
3.1.1题目解析
对于这个题目，我们要知道这个题目的要求是要在给定数组中找到两个下标不同的元素，其之和为给定数字，并将其下标进行返回。
3.1.2 算法原理
首先，当我们拿到这道题目的时候第一个想到的就是暴力穷举法，通过两层循环，来判断是否与target相等，时间复杂度为O(N²)
但是要怎么优化呢，就可以通过双指针的方法。第一，我们会发现这个数组是固定长度；其次在进行双指针之前，我们需要先对数组进行一个升序的排序（降序也可以），排序之后，我们就会发现其实有些穷举是没有必要的。我们以排完序的数组为例：2,5,8,15,16，在这之中我们想找和为7的两个数字，当我们将2和5加起来等于7的时候，对于后面的数字的其实我们就无需考虑了，因为这是一个升序的数组，后面的数字之和一定会比2和5加起来大，这也是我们优化的地点。
那么代码具体是如何实现呢：
1.对给定数组进行升序排序
2.采取双指针left和right，分别指向数组的开头和结尾，即最小和最大的元素
3.如果他们之和大于所需数字，left指针++；小于则right指针--，直至left指针与right指针位置相交，即说明当前数组内不存在符合需求的两个数字。
图示如下：
找到了
没找到
3.1.3 具体代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
for(int i=0;i<nums.size();++i)
{
//对nums[i]去重
if(i>0&& nums[i]==nums[i-1]) continue;
// -4 -1 -1 0 1 2
//找和为nums[-i]的
cout<<i<<" ";
if(nums[i]>0) break;
int left=i+1;
int right=nums.size()-1;
while(left<right)
{
if(nums[left]+nums[right]==-nums[i]) {
ret.push_back({nums[i],nums[left],nums[right]});
right--;
//对num[right]去重
while(nums[right]==nums[right+1])
{
right--;
if(left>right) break;
}
}
else if (nums[left]+nums[right]>-nums[i]) right--;
else left++;
}
}
return ret;
}
};3.2 三数之和
15. 三数之和 - 力扣（LeetCode）
3.2.1题目解析
本题目的要求是我们要在指定数组中找到三个元素和为0的元素组，且返回的三元组不得重复，像【0,2，-2】和【2,0，-2】就只能返回其一。
3.2.2算法原理
本题采取暴力穷举需要三重循环，即时间复杂度为O（N³），但是用双指针的方法可降至O(N²)
实现思路：
1.对指定数组排序
2.遍历指定数组
3.在遍历数组的同时，使用双指针求和为其相反数的两个元素，找到则将这三个元素存进容器。
3.2.3具体代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
for(int i=0;i<nums.size();++i)
{
//对nums[i]去重
if(i>0&& nums[i]==nums[i-1]) continue;
// -4 -1 -1 0 1 2
//找和为nums[-i]的
cout<<i<<" ";
if(nums[i]>0) break;
int left=i+1;
int right=nums.size()-1;
while(left<right)
{
if(nums[left]+nums[right]==-nums[i]) {
ret.push_back({nums[i],nums[left],nums[right]});
right--;
//对num[right]去重
while(nums[right]==nums[right+1])
{
right--;
if(left>right) break;
}
}
else if (nums[left]+nums[right]>-nums[i]) right--;
else left++;
}
}
return ret;
}
};3.3 四数之和
18. 四数之和 - 力扣（LeetCode）
3.3.1题目解析
本题与上一题类似，只不过由三个数变成四个数
3.3.2算法原理
本题采取暴力穷举需要四重循环，即时间复杂度为O（N^4），但是用双指针的方法可降至O(N^3)
实现思路：
1.对指定数组排序
2.双重遍历指定数组
3.在遍历数组的同时，使用双指针求和为其两次遍历相反数的两个元素，找到则将这四个元素存进容器。
3.3.3具体代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
sort(nums.begin(),nums.end());
size_t sz=nums.size();
//解决溢出问题_longlong
for(size_t i=0;i<sz;)
{
//转变求三数和
//!取消常规++逻辑，由自己来控制，不然会多加一次
for(int j=i+1;j<sz;)
{
//转变为求两数和
long long target1=(long long)target-nums[i]-nums[j];
int left=j+1;
int right=sz-1;
while(left<right)
{
if(nums[left]+nums[right]==target1)
{
ret.push_back({nums[i],nums[j],nums[left],nums[right]});
right--;
//对num[right]去重
while(nums[right]==nums[right+1])
{
right--;
if(left>right) break;
}
}
else if (nums[left]+nums[right]>target1) right--;
else left++;
}
j++;
while(j<sz && nums[j]==nums[j-1]) j++;
}
i++;
while(i<sz && nums[i]==nums[i-1]) i++;
}
return ret;
}
};
三、结语
到此为止，对于双指针的讲解已完成一部分，下一部分我们将在下一节继续讲解