双指针算法（部分例题解析)

快慢指针+左右指针

---

前言

双指针，它通过设置两个指针来遍历数据，从而实现高效的查找、排序、去重等操作。双指针算法的核心在于通过合理地移动这两个指针，减少不必要的遍历，提高算法的效率。

---

283. 移动零 - 力扣（LeetCode）283. 移动零 - 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 1:输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:输入: nums = [0]输出: [0] 提示: * 1 <= nums.length <= 104 * -231 <= nums[i] <= 231 - 1 进阶：你能尽量减少完成的操作次数吗？https://leetcode.cn/problems/move-zeroes

知识点:在数组中，我们是利用数组下标来充当指针的。指针目的是锁定某个值,在数组中,下标，1.同样可以锁定值

这跟那个快速排序的前后指针相似，不过这里dest指向cur的后面，而在快速排序中cur在prev的前面，这里就是cur在dest的前面

 让dest一开始为-1,因为cur要从第一个元素开始判断,那你dest只能放在cur到后面那就是负一

void Swap(int *q,int *p)
{int tmp=*q;*q=*p;*p=tmp;
}
void moveZeroes(int* nums, int numsSize) {int dest=-1;for(int cur=0;cur<numsSize;cur++){if(nums[cur]){Swap(&nums[++dest],&nums[cur]);}}
}

---

1089. 复写零 - 力扣（LeetCode）1089. 复写零 - 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。 示例 1：输入：arr = [1,0,2,3,0,4,5,0]输出：[1,0,0,2,3,0,0,4]解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]示例 2：输入：arr = [1,2,3]输出：[1,2,3]解释：调用函数后，输入的数组将被修改为：[1,2,3] 提示： * 1 <= arr.length <= 104 * 0 <= arr[i] <= 9https://leetcode.cn/problems/duplicate-zeros

由于0要写两次，所以，找到复写零后面末尾的元素是谁，就是0复写了，以后数组末尾的数字是谁，在这个数字后面的数字就不重要了，我们可以从后往前完成复写，让需要保留的数字，覆盖到不需要保留的数字上。

所以要先找到最后一个复写的数

第一步，先判断cur的位置
第二步，决定dest是向前走一步，还是两步
第三步，判断dest是否已经结束
第四步，cur++

 但是还有一种情况就是当，复写零最后一个结尾数字是0的时候dest走两步已经走到数组外了，还没有判断的机会就出界了，所以要多加一个判断

void duplicateZeros(int* arr, int arrSize) {int cur=0,dest=-1;//让dest=-1，这样就能做到，cur不是0 ,dest就在这一步，如果是0的话，dest就要比cur多走一步,最终有几个零就多走了几步while(cur<arrSize){if(arr[cur]==0)dest++;dest++;if(dest>=arrSize-1)//确定边界,当dest走到size-1的时候就已经找到了边界，也就是最后一个元素，这时我们就跳出循环,当然也有可能他超出了边界break;cur++;}if(dest!=arrSize-1)//如果dest出界了，我们就让dest到n- 1的位置上去,也可以直接写成: n-1=0,dest-=2;cur-=1{arr[arrSize-1]=0;cur--;dest-=2;}while(cur>=0){if(arr[cur])arr[dest--]=arr[cur--];else{if(dest-1>=0)arr[dest--]=0;if(dest-1>=0)arr[dest--]=0;cur--;}}
}

 可以联想一道题：a数组是升序的，b数组也是升序的，a数组里面的长度特意扩大了，数组长度确保能够容纳b，就是要让我们把a，b数组以升序的方式写进a中,他的方法也是从尾部开始比较，大的插入

---

202. 快乐数 - 力扣（LeetCode）202. 快乐数 - 编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为： * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 * 如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。 示例 1：输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1示例 2：输入：n = 2输出：false 提示： * 1 <= n <= 231 - 1https://leetcode.cn/problems/happy-number

 攻破点：一个正整数，一直这样下去会循环下去，也就是会出现两个重复的数字，会形成一个圈，一直在圈里面打转，如果说在这个过程中出现的一个结果是1，但还不是会无限循环下去，所以无论是快乐树，还是不快乐数，最后都会循环成环，只不过在，快乐数中，环中的数字都是1

在链表中，有一道题是判断链表是否成环，还有一道题是返回链表成环的起始位置，那两道题中，我们都用到了快慢指针，所以这道题也可以用快慢指针

快慢指针：

快指针和慢指针从同一个起点开始。快指针每次移动两步，慢指针每次移动一步

快指针比慢指针快一步，所以他们相对速度是一步，所以如果是有环的话，快指针是一定会追上慢指针的，所以我们这道题的思路是用快慢双指针法，当快慢指针相遇时，看所处的值是不是1

int func(int n)
{int sum=0;while(n){int tmp=n%10;sum+=tmp*tmp;n/=10;}return sum;
}
bool isHappy(int n) {int slow=n;int fast=func(n);while(slow!=fast){slow=func(slow);fast=func(func(fast));}return slow==1;
}

---

 11. 盛最多水的容器 - 力扣（LeetCode）11. 盛最多水的容器 - 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。 示例 1：[https://aliyun-lc-upload.oss-cn-hangzhou.aliyuncs.com/aliyun-lc-upload/uploads/2018/07/25/question_11.jpg]输入：[1,8,6,2,5,4,8,3,7]输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1]输出：1 提示： * n == height.length * 2 <= n <= 105 * 0 <= height[i] <= 104https://leetcode.cn/problems/container-with-most-water

如果按一开始暴力的思路做的话，就定住一个边，然后变化其他的边，然后把面积最大值记录下来，然后再换下一个边，时间复杂度明显是o(n^2)， 时间会超

设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ：

S(i,j)=min(h[i],h[j])×(j−i)

他这个就像那个木桶装水一样，一个木桶能装多少水，取决于他最短那个板子长度

定义两个指针在数组的两边计算出它那个面积之后，哪边长度短就移动哪边，让他到下一个数上去，因为如果长度短的不移动，另一边也就是，移动长的，那他之后算下来的面积只有可能小于原来的值，你就好比于你一个木桶的短木板在那里，你周围木板再怎么换，只有可能小于原来装的水的量，跟这个是一个思路，这样时间复杂度就只有o(n)

int minfunc(int q,int p,int gap)//S(i,j)=min(h[i],h[j])×(j−i)
{if(q>=p)return p*gap;elsereturn q*gap;
}
int maxArea(int* height, int heightSize) {int left=0;int right=heightSize-1;int max=minfunc(height[left],height[right],right-left);while(left<right){int tmp=minfunc(height[left],height[right],right-left);if(tmp>max)max=tmp;if(height[left]>height[right])right--;else left++;}return max;
}

---

611. 有效三角形的个数 - 力扣（LeetCode）611. 有效三角形的个数 - 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。 示例 1:输入: nums = [2,2,3,4]输出: 3解释:有效的组合是: 2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3示例 2:输入: nums = [4,2,3,4]输出: 4 提示: * 1 <= nums.length <= 1000 * 0 <= nums[i] <= 1000https://leetcode.cn/problems/valid-triangle-number

思路：一开始数很乱啊，其次条件符合a+b大于c ， b+c大于a , a+c大于b 要判断三次，如果是有序的话，那就只需要两个小的数，大于最大的数即可

 例：2     2     3     4     5     9    10

定义两个指针，left在第一个和right倒数第二,最后一个数字定为max

如果此时left+right是大于max的，那么right和left中间的数字，加上right都会大于max，然后让right-- ,  去找比right小一点的数说，相反，如果不大于的话就要提升left

count就+=(right-left )加上他们中间的数字

等到把10的情况都找到之后，也就是while(left<right)结束后再固定9

int triangleNumber(int* nums, int numsSize) {int gap=numsSize;while(gap>1)//.....Sort{gap/=2;for(int i=0;i<numsSize-gap;i++){int end=i;int tmp=nums[end+gap];while(end>=0&&nums[end]>tmp){nums[end+gap]=nums[end];end-=gap;}nums[end+gap]=tmp;}}int count=0;for(int i=numsSize-1;i>1;i--){int a=0;int b=i-1;while(a<b){if(nums[a]+nums[b]>nums[i]){count+=(b-a);b--;}else{a++;}}}return count;
}

---

和为S的两个数字_牛客题霸_牛客网输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/2494110081745073766147第一步，先将数组排序

第二步，两指针向中间移动

使用双指针指向数组第一个元素和最后一个元素，然后双指针对撞移动，如果两个指针下的和正好等于目标值sum，那我们肯定找到了，如果和小于sum，说明我们需要找到更大的，那只能增加左边的元素，如果和大于sum，说明我们需要找更小的，只能减小右边的元素。

• 准备左右双指针分别指向数组首尾元素。
• 如果两个指针下的和正好等于目标值sum，则找到了所求的两个元素。
• 如果两个指针下的和大于目标值sum，右指针左移；如果两个指针下的和小于目标值sum，左指针右移。
• 当两指针对撞时，还没有找到，就是数组没有。

int* FindNumbersWithSum(int* array, int arrayLen, int sum, int* returnSize ) {// write code hereint *arr=(int *)malloc(sizeof(int)*2);int left=0;int right=arrayLen-1;while(left<right){if(array[left]+array[right]>sum)right--;else if(array[left]+array[right]<sum)left++;else{arr[0]=array[left];arr[1]=array[right];*returnSize=2;break;}}return arr;}

那如果是三数之和呢？

那就是定第一个数为num，在后面的区间中用二数之和的思路找到和为-num，的两个值

那如果是四数之和呢?

那就是定第一个数为num，后面区间中用三数之和的思度找

总结:

•  双指针算法通常可以将时间复杂度从 O(n^2) 降低到 O(n) 。例如，在有序数组中查找两数之和，暴力解法需要两层循环，而使用左右指针只需要一层循环。
• 空间效率高,它不需要额外的存储空间，只需要两个指针变量，空间复杂度一般为 O(1) 。