欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之双指针(一)
发布时间：2025.4.4
隶属专栏：算法
目录
双指针算法介绍
常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。
对撞指针：
⼀般⽤于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
left == right（两个指针指向同一个位置）left > right（两个指针错开）
快慢指针：
又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的⼀种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
例题
移动零
题目链接
题目描述
给定一个数组
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进阶：你能尽量减少完成的操作次数吗？
算法思路
在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零数序列的最后一个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在 cur 遍历期间，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。
代码实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for(int dest = -1, cur = 0; cur < n; cur++)
{
if(nums[cur] != 0)
{
swap(nums[dest+1], nums[cur]);
dest++;
}
}
}
};
复写零
题目链接
题目描述
给你一个长度固定的整数数组
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 <= 1040 <= arr[i] <= 9
算法思路
如果从前向后进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。但是从后向前复写的时候，我们需要找到最后一个复写的数，因此我们的大体流程分两步：
- i. 先找到最后一个复写的数；
- ii. 然后从后向前进行复写操作。
代码实现
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
int cur = 0, dest = -1;
// 找到最后覆写的数
while(dest < n)
{
if(arr[cur] == 0)
dest+=2;
else
dest++;
if(dest >= n-1)
break;
cur++;
}
// 特殊情况处理
if(dest == n)
{
arr[n-1] = 0;
dest-=2;
cur--;
}
// 进行复写操作
while(cur >= 0)
{
if(arr[cur] == 0)
{
arr[dest--] = 0;
arr[dest--] = 0;
cur --;
}
else
{
arr[dest--] = arr[cur--];
}
}
}
};
快乐数
题目链接
题目描述
编写一个算法来判断一个数
n是不是快乐数。
快乐数 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n是 快乐数 就返回true；不是，则返回false。
示例 1：输入：
n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1示例 2：
输入：
n = 2
输出：false提示：
1 <= n <= 231 - 1
算法思路
根据上述的题目分析，我们可以知道，当重复执行 x的时候，数据会陷入到一个循环之中。而快慢指针有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是1 ，那么这个数一定是快乐数；如果相遇位置不是1的话，那么就不是快乐数。
代码实现
class Solution {
public:
int BitSum(int n)
{
int num = 0;
while(n>0)
{
int x = n %10;
n /= 10;
num+=x*x;
}
return num;
}
bool isHappy(int n) {
int slow = n, fast = BitSum(n);
while(slow != fast)
{
slow = BitSum(slow);
fast = BitSum(BitSum(fast));
}
return slow == 1;
}
};
盛最多水的容器
题目链接
题目描述
给定一个长度为
n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：
[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.length2 <= n <= 1050 <= height[i] <= 104
算法思路
设两个指针 left ，right分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left])
容器的左边界为 height[left] ，右边界为 height[right] 。
为了方便叙述，我们假设左边边界小于右边边界。
如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：
- 容器的宽度⼀定变小。
- 由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是⼀定不会超过右边的柱子高度，因此容器的容积可能会增大。
- 如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会
超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小的。
由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。
当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案。
代码实现
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size()-1;
int ret = 0;
while(left < right)
{
int v = min(height[right], height[left]) * (right-left);
ret = max(ret, v);
if(height[left] < height[right])
left++;
else
right--;
}
return ret;
}
};
⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！