优选算法——双指针

前言

本篇博客为大家介绍双指针问题，它属于优选算法中的一种，也是一种很经典的算法；算法部分的学习对我们来说至关重要，它可以让我们积累解题思路，同时也可以大大提升我们的编程能力，本文主要是通过一些题目来为大家介绍，这里统一说明一下，每一道题我会粘贴原题链接，大家可以先做再来看解析，这样会更有针对性，下面进入正文。

1. 移动零

题目链接：. - 力扣（LeetCode）

题目解析：本题大家读完后应该可以很轻松地理解题目的意思，我们需要将0全部移动到数组的末尾，并且保持其他元素的顺序是不能改变的。

算法原理：这类题可以划归为数组分块问题，对于这类问题，首先想到的方法就是双指针，大家注意这里提到的指针并不是我们在C语言中学过的那个指针，这里的“指针”代表数组的下标。我们需要定义两个“指针”，一个指针用于遍历数组，另一个指针用来存储非零元素的最后一个位置，这两个“指针”会将整个数组划分为3个区间。

具体大家来看下图：

区间划分完后，我们需要让两个“指针”移动的过程中保持它们本身的性质，这样我们就可以解决这个问题，那么我们该如何保持呢？

大家可以结合题目给的例子来进行理解，上面的思路就是双指针的核心思路。

代码实现：

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur=0;int dest=-1;for(cur=0;cur<nums.size();cur++){if(nums[cur]){swap(nums[++dest],nums[cur]);}}}
};

这里使用C++实现代码，一个for循环就搞定了，主要就是在于指针的调整。

2. 复写零

题目链接：. - 力扣（LeetCode）

题目解析：本题要求我们来对0进行复写，其实就是遇到0了抄两遍，不是0就抄一遍，注意题目要求就地修改，不能开辟新的数组。

算法原理：首先我们需要定义两个指针，其次需要找到最后一个复写的数，最后从后向前进行复写操作，具体大家请看下图：

这里大家要注意，我们在找最后一个复写的数的时候也同样需要用到双指针算法；其中有越界的情况，我们要进行特殊处理。

代码实现：

class Solution {
public:void duplicateZeros(vector<int>& arr){//第一步：找最后一个复写的数int cur=0;int dest=-1;int n=arr.size();while(dest<n){if(arr[cur]){++dest;}else{dest+=2;}if(dest>=n-1){break;}cur++;}//第二步：处理边界if(dest==n){arr[n-1]=0;cur--;dest-=2;}//第三步：从后向前复写while(cur>=0){if(arr[cur]){arr[dest--]=arr[cur--];}else{arr[dest--]=0;arr[dest--]=0;cur--;}}}
};

这里大家看到代码，分为三部分：找最后一个复写的数、处理边界以及复写操作；还有一个小问题，有同学会想为什么必须从后往前进行复写，不能从前往后吗？

答案是不可以，大家思考一下，如果从前往后复写，那么0要写2遍，这个时候我们原始的数据就会被覆盖，这样就无法达到题目的要求。

3. 快乐数

题目链接：. - 力扣（LeetCode）

题目解析：本题要求我们判断一个数是否为快乐数，那么我们首先要明确什么是快乐数；然后我们进行判断，是快乐数返回1，否则返回0。

算法原理：这道题我们也可以使用双指针来解决，具体来说就是快慢指针，大家可以先回想一下我们在链表的学习中遇到的这么一道题，题目要求我们判断环形链表，当时我们使用了快慢指针的方法来解决，那么本题我们同样可以使用这种思想来解决。根据之前的结论，大家首先需要明确，当我们不断进行题目要求的操作时，一定会进入一个循环，这里要么是1一直循环；要么是循环其他不为1的数据，所以每次计算得到的数可以串起来看成一个“链表”，这样就和我们之前说过的环形链表殊途同归了。我们只需要定义一个慢指针，一个快指针，在循环的过程中，快指针一定会追上慢指针，我们判断相遇的时候的值是不是1，即可判断给定的数是不是快乐数。

 

代码实现：

class Solution 
{
public:int test(int n){int sum=0;while(n){int t=n%10;sum+=t*t;n/=10;}return sum;}bool isHappy(int n) {int slow=n;int fast=test(n);while(slow!=fast){slow=test(slow);fast=test(test(fast));}return slow==1;}
};

这里补充一个小问题，就是实现题目中要求的操作，每一位的平方和相加，这个想必大家在C语言阶段就已经接触过，这里大家看代码应该很容易理解。

4. 盛水最多的容器

题目链接：. - 力扣（LeetCode）

题目解析：本题要求找到盛水最多的容器，本质就是让我们找出两个数来确定一个容器，使这个容器的“容积”最大；那么本题大部分人的第一反应就是暴力枚举，把每一个乘积都求出来，然后对比找出最大的，这是一种很容易理解的思路，但是代码的时间复杂度会非常高，效率就比较低，所以不可行。

算法原理：本题我们要使用双指针来解决问题，具体是运用左右指针，一个指针从左往右，另一个指针从右往左，两个指针向中间靠拢，哪边高度小哪边就往里动，下面说明了这样做的原理，利用了单调性来找到规律。

代码实现：

class Solution {
public:int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int ret=0;while(left<right){int v=min(height[left],height[right])*(right-left);ret=max(ret,v);if(height[left]<height[right]){left++;}else{right--;}}return ret;}
};

5. 有效三角形的个数

题目链接：. - 力扣（LeetCode）

题目解析：本题要求我们在一组数中选出可以构成三角型的数字组合，其实就是求有多少种选法，这里大家注意看例子的提示，重复选的数也是OK的，只要是不同位置的数就满足条件。

算法原理：

本题我们不能使用暴力解法来做，那样时间复杂度太高，效率很低；那么我们进行优化，使用双指针来解决问题，具体流程大家可以看下图，首先我们先将数据进行排序，再来固定最大的数，然后定义左右两个指针，根据两种不同的情况移动指针，循环操作，就可以解决本题。

代码实现：

class Solution {
public:int triangleNumber(vector<int>& nums) {//排序sort(nums.begin(),nums.end());int ret=0;int n=nums.size();for(int i=n-1;i>=2;i--)//固定最大数{int left=0;int right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){ret+=right-left;right--;}else{left++;}}}return ret;}
};

6. 查找总价格为目标值的两个商品

题目链接：. - 力扣（LeetCode）

题目解析：本题的要求很简单，就是让我们在一组数中找到两个数，使它们的和等于目标值。

算法原理：本题其实大部分人第一时间还是会想到暴力解法，运用了两个循环，遍历所有情况，判断是否等于target，这样做很好理解，但是代码的时间复杂度会很高，会超时，所以这种暴力解法不建议。优化版的解法就是使用双指针，定义左右指针，分为三种情况来决定指针的移动，具体大家请看下图。

代码实现：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n=price.size();int left=0;int right=n-1;while(left<right){if(price[left]+price[right]<target){left++;}if(price[left]+price[right]>target){right--;}if(price[left]+price[right]==target)return {price[left],price[right]};}return {-1,-1};}};

总结

本篇博客为大家介绍了双指针算法，它可以帮助我们解决很多原本复杂的问题，大家需要掌握这种思想，当我们遇到需要将数据分区间进行处理的时候，我们可以考虑双指针，这其中还包括了快慢指针的思路，最后希望本篇博客可以为大家带来帮助，感谢阅读！