前言：
双指针一般在做与数组有关的题是经常容易用到的，在很多场景下都能得到很好的应用，下面我将通过多个多指针的题（力扣上面的），来总结一下双指针的原理和使用场景
需知：我在讲解一个题时主要分为三步：题意解析、讲解算法原理和编写代码
目录
一. 复写0
1.1 题意解析
力扣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 <= 1040 <= arr[i] <= 9
题目的重点就是如何在不改变数组长度的情况下将0复写一遍，并将非0元素右移
1.2 算法原理
编写代码
void duplicateZeros(vector<int>& arr) {
//1.先找到最后一个数
int cur = 0, dest = -1, n = arr.size();
while (cur < n){
if (arr[cur]) dest++;
else dest += 2;
if (dest >= n - 1) break;
cur++;
}
//2.处理一下边界问题
if (dest == n){
arr[n - 1] = 0;
cur--; dest -= 2;
}
//3.从后往前完成复写操作
while (cur >= 0){
if (arr[cur]){
arr[dest] = arr[cur];
dest--; cur--;
}
else{
arr[dest] = arr[dest - 1] = 0;
dest -= 2; cur--;
}
}
}
二、快乐数
题意解析
力扣 202
题目描述
编写一个算法来判断一个数
n是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n是 快乐数 就返回true；不是，则返回false。示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
算法原理
编写代码
int bitSum(int x) {
int sum = 0;
while (x > 0)
{
sum += (x % 10) * (x % 10);
x /= 10;
}
return sum;
}
bool isHappy(int n) {
int fast = bitSum(n), slow = n;
while (slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
三、盛最多水的容器
题意解析
力扣11
给定一个长度为
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
算法原理
代码实现
int maxArea(vector<int>& height) {
int slow = 0, fast = height.size() - 1;
int ret = 0;
while (slow < fast)
{
int capacity = min(height[slow], height[fast]) * (fast - slow);
ret = max(ret, capacity);
if (height[slow] < height[fast]) ++slow;
else --fast;
}
return ret;
}
四、有效三角形个数
题意解析
力扣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 <= 10000 <= nums[i] <= 1000
算法原理
代码实现
int triangleNumber(vector<int>& nums) {
int ret = 0;
sort(nums.begin(), nums.end());
for (int i = nums.size() - 1; i >= 2; i--)
{
int left = 0, right = i - 1;
while (left < right)
{
if (nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else left++;
}
}
return ret;
}
五、总结
以上就是双指针在oj刷题中常见的几个题，通过这几个题，我们可以观察到双指针的题在处理数组划分，还有数组操作中经常用到，在我们平时做数组相关的题时要有往双指针这方面想的意识
感谢各位大佬观看，创作不易，还望各位大佬点赞支持！！！
标签：arr,slow,oj,int,cur,height,dest,指针,刷题 From： https://blog.csdn.net/2301_80220607/article/details/142058671