【从零开始的算法学习日记✨优选算法篇✨】第一章：双指针技巧
✨放在开头：
【从零开始的算法学习日记】系列将包含四个篇章，分别是【优选算法篇】、【递归/搜索/回溯算法篇】、【动态规划篇】以及【贪心算法篇】，每一篇章下面都会有若干章节以及数十道例题详解，博主计划在明年开春前陆续出完这些章节，欢迎大家订阅关注，敬请期待！
作为算法小白一枚，博主的初心是记录自己的学习历程，分享每一步的成长与心得。如果文章内容对你有所帮助，那将是我的荣幸。让我们一起加油，共同进步！passion！💪
🌈 个人主页：谁在夜里看海.
⛰️ 丢掉幻想，准备斗争
目录
一、算法思想
何为双指针？
双指针算法是指用两个指针来遍历数组或链表的算法技巧，一般可分为同向双指针、对向双指针以及快慢双指针。双指针算法的核心是减少时间复杂度，提高算法效率，下面会有例题进行印证。
注意：双指针算法不一定就是使用指针进行遍历，也可以通过下标等其他形式，双指针只是一个思想，并不只局限于指针。
同向双指针
两个指针从同一侧开始遍历，其中一个指针先进行移动，符合条件时，另一个指针跟上，此时两个指针会将数据划分为三块区间，前两块为处理过的区间，后一块为待处理区间：
对向双指针
两个指针分别从数组的头和尾开始向中间移动，直到它们相遇，这种方法常用于有序数组中，解决需要寻找满足特定条件的两个元素的问题，利用数组单调性，判断两个指针的移动条件。
典型例题：两数之和，如果两个指针指向的元素之和小于目标值，则移动左指针增大和；如果大于目标值，则移动右指针减小和：
快慢双指针
一个指针移动速度快，一个指针移动速度慢（一般快指针速度为慢指针的2倍），常用于判断链表或数组中是否存在回环结构。
典型例题：判断链表中是否有环，如果有环，快指针会追上慢指针，如果无环，快指针会到达链表末端：
双指针可以将很多需要双重循环的情况优化成单次遍历，减少时间复杂度：O(n^2) -> O(n)
下面来看看双指针算法的具体运用：
二、具体运用
1.移动零
难度等级：⭐⭐⭐
题目链接：283.移动零
题目描述：
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
例如：
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]
算法思路
在这道题中，我们可以使用双指针中的同向双指针，用一个cur指针扫描整个数组，另一个dest指针指向非零序列的最后一个位置，此时dest、cur指针划分的三个区间分别为：非零序列，零序列以及待操作序列。当然 这里的指针并非真的指针，可以用数组下标表示。
算法流程
①：将cur初始化为0，指向数组首元素；dest初始化为-1，因为序列未进行操作，我们不知道非零序列的最后一个位置在哪。
②：cur依次向后进行遍历，遇到0元素跳过；遇到非0元素时，dest指针++，交换cur以及dest位置的数据，之后cur继续遍历：
a.遇到元素为0：为什么跳过呢？我们要让 [dest+1,cur-1] 区间元素全为0，遇到0元素cur++，此时cur-1的位置就是0，符合要求。
b.遇到元素不为0：dest++，并交换dest与cur指向的元素，然后cur++：dest++后，其指向的元素一定是0，与cur的非0元素交换，然后cur++，使得dest指向非零元素，cur-1指向零元素，满足区间序列要求：
代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur = 0;
int dest = -1;
for(cur,dest;cur!=nums.size();++cur)
{
if(nums[cur]) // cur非零，交换元素
swap(nums[++dest],nums[cur]);
// cur为零，跳过
}
}
};2.复写零
难度等级：⭐⭐⭐
题目链接：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：单指针遍历
用cur指针从前往后遍历数组，遇到0元素时，将该元素后面的元素全部向后移一位，然后将cur+1的元素赋为0，cur+=2，继续遍历。这种方法是最容易想的，但是时间复杂度较高，为O(n^2)，为了提高时间复杂度，优化算法，我们可以用双指针思想。
思路2：双指针
我们的想法是用cur指针遍历数组，dest指针指向非零序列最后位置，当cur遇到0时，将dest+1、dest+2位置全部赋为0，cur++两次，然后继续遍历。这个思路有没有什么漏洞呢？由于是原地复写操作，dest复写时会将一个数据覆盖，导致该数据丢失，不能满足题目要求（其余元素向右平移），因此从前向后的遍历复写不可行。
既然从前向后遍历不行，那么从后向前呢：
从后向前遍历需要经过这两步：① 确定cur、dest的初始位置，cur不能为0了，因为要从后向前，也不能为n-1，这样就和上面操作没区别了；② 找到初始位置后开始遍历复写
算法流程
①：初始化指针，cur为0，dest为-1；
②：cur向后遍历，判断cur位置的元素：
a.如果为0，dest往后移两位
b.不为0，dest往后移一位；
直到dest来到数组末尾。
ps：上述过程其实就是从前向后遍历复写的操作，只不过不在这里完成复写
③：确定好cur与dest位置后，cur从后向前开始遍历：
a.如果为0，dest与dest-1位置修改为0，dest-=2，cur--
b.不为0，dest与cur交换元素，dest--，cur--
注意：上述过程仍然存在漏洞，假设数组为 [1,0,2,3,0,0,5,0]，经过①②操作会产生什么结果：
此时dest越界访问了！所以我们要对这种情况进行特殊处理，在②③之间加上特殊处理操作。
对越界的特殊处理：
① cur-1位置值修改为0
② cur--
③ dest-=2
代码
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
// 初始化指针
int cur = 0;
int dest = -1;
for(cur,dest;dest < (int)arr.size()-1;++cur)
{
// 模拟从前向后遍历过程
if(arr[cur])
++dest;
else
dest += 2;
}
// 由于dest抵达位置时，for循环内部cur多执行了一次++，要减去
--cur;
if(dest==arr.size()) // 越界处理
{
arr[--dest] = 0;
--cur;
--dest;
}
for(cur,dest;dest>0;--cur)
{
// 不为0，交换元素
if(arr[cur])
swap(arr[cur],arr[dest--]);
// 为0，复写
else
{
arr[dest--] = 0;
arr[dest--] = 0;
}
}
}
};3.快乐数
难度等级：⭐⭐⭐
题目链接：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示例 2：
输入：n = 2 输出：false
算法思路
n = 19：19-> 82 -> 68 -> 100 -> 1 -> 1 ->......（无限循环1）
n = 2： 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 ->......（出现重复数字4，之后开始循环）
根据上述分析，可以发现什么？这不就是一个回文结构嘛，快乐数的回文串里面只有1，判断n是否为快乐数，只需要判断回文串数字即可：回文传内但凡有其他元素，就不为快乐数
判断回文串，用快慢双指针，两个指针交汇处一定在回文串内，然后根据交汇元素就可以得出结果
算法流程
①：初始化快慢指针，slow为0，指向第一个元素；fast为1，指向第二个元素？：这并不是一个数组，所以不能这么初始化×
正确的初始化：定义一个函数sum，返回参数的平方，slow为sum(n)，表示第一个数；fast为sum(sum(n))表示第二个数；
②：模拟向后遍历过程->当slow = sum(slow)，向后遍历一个；fast = sum(sum(fast))，向后遍历两个，直到slow与fast相等（根据鹊巢定理，slow与fast必定相遇）
代码
class Solution
{
public:
int bitSum(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, fast = bitSum(n);
while(slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
};4.盛⽔最多的容器
难度等级：⭐⭐⭐⭐
题目链接：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
算法思路
题目的意思就是在数组中找到两个数，使其中较小数与下标差的乘积（即容量）为最大。
思路一：暴力枚举
将所有的情况全部枚举一遍，在所有情况中找出那个最大值，这是最简单最暴力的解法，但此时时间复杂度为O(n^2)，但是这道题目不允许我们使用暴力解法，这样会导致超时，所以就需要我们优化算法，寻找一种时间复杂度更少的解法：
思路二：对向双指针
我们可以用双指针思想进行算法优化，时间复杂度会降到O(n)，在这道题，我们怎么巧妙使用呢？
这道题的本质是在数组中寻找两个符合条件的数，前面说到，对向双指针常用于有序数组中，解决需要寻找满足特定条件的两个元素的问题，完全符合，只不过题目所给的不是有序数组，我们只需用sort函数把它变有序即可。
我们寻找的两个数需要考虑以下因素：
① 较小数的大小（水桶的短板决定容量），即为高
② 两数的下标之差，即为底
水桶容积为：底×高 ，我们要使得乘积最大。
当底和高同时变化时，我们无法进行判断，所以我们首先要控制变量，很明显，底是更好控制的，这时候就要用到我们的对向双指针：
left指针初始指向首元素，right指针初始指向尾元素，此时是底最大的情况，决定容积的就是left和right指向元素的较小值，即短板（高），如果短板固定了，另一个指针再怎么移动，容积只会减小（高不变，底一直减小），所以我们要移动短板的指针，才可能找到更大的容积：
我们每一次移动后的情况都可能是最大容积，所以需要实时记录，最后取最大值。
算法流程
①：初始化左右指针，left为0，指向首元素；right为n-1，指向尾元素；
②：记录当前位置的容积；
③：判断左右指针指向元素的大小：
a.若left指向元素更小，++left
b.若right指向元素更小，--right
④：left、right相遇停止。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
// 初始化指针
int left = 0,right = height.size()-1;
vector<int> cubage; // 记录容积的数组
while(left != right)
{
// 高为较小值
int h = height[left] < height[right] ? height[left]: height[right];
// 底为下标之差
int w = right-left;
cubage.push_back(h*w); // 记录容积
if(height[left]<height[right])
++left;
else
--right;
}
int max = 0;
// 找最大值
for(auto it:cubage)
{
if(it>max)
max = it;
}
return max;
}
};5.有效三⻆形的个数
难度等级：⭐⭐⭐⭐
题目链接：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
算法思路
题目让我们在数组中找到所有可以组成三角形的三元组，换而言之，就是让我们找三个数，满足任意两个数之和>第三个数。
思路一：暴力枚举
最容易想到的还是暴力解法，但是在这道题，暴力枚举的时间复杂度来到了O(n^3)，性能低下，这种方法我们不考虑，需要寻找更优算法
思路二：对向双指针
三角形的满足条件为：任意两个数之和>第三个数，但其实只需要让 较小两个数之和>最大数 即可，我们可以固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找 出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边：
算法流程
①：固定三角形最长边，cur初始化为n-1；在其左区间初始化左右指针，left为0；right为cur-1；
②：判断left和right指向元素之和：
a.>最长边，记录三元组，right--
b.<最长边，left++
③：；left、right相遇停止；
④：cur--，重复上述流程。
代码
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int cur = nums.size()-1,sum = 0;
for(cur;cur > 1;--cur)
{
int left = 0,right = cur-1;
while(left != right)
{
if(nums[left]+nums[right] > nums[cur])
{
sum += (right-left);
--right;
}
else
++left;
}
}
return sum;
}
};6.总价值为目标值的两个商品
难度等级：⭐⭐⭐
题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
题目描述：
购物车内的商品价格按照升序记录于数组
price。请在购物车中找到两个商品的价格总和刚好是target。若存在多种情况，返回任一结果即可。示例 1：
输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]
算法思路
这道题目就是典型的对向指针应用场景，利用有序数组的单调性，移动左右指针
算法流程
①：初始化左右指针，left为0；right为n-1；
②：判断指向元素之和：
a.若>目标值，left++(让和增大)
b.若<目标值，right--(让和减小)
c.若=目标值，记录，left++，right--
③：相遇或交错时停止。
代码
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0,right = price.size()-1;
vector<int> ret;
while(left != right)
{
if(price[left]+price[right] == target)
{
ret.push_back(price[left]);
ret.push_back(price[right]);
break;
}
else if(price[left]+price[right] > target)
--right;
else
++left;
}
return ret;
}
};7.三数之和
难度等级：⭐⭐⭐⭐
题目描述：
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
算法思路
思路一：暴力枚举
又是经典开头，暴力解法，我们来分析一下这道题暴力解法的时间复杂度：找三个元素进行组合，就要嵌套三层循环，时间复杂度为O(n^3)，根据前面题目的经验，我们可以通过双指针算法将时间复杂度减到O(n^2)：
思路二：双指针
和例题5相似，这道题也是要寻找符合条件的三元组，所以可以套用例题5的解法：① 固定一个数
② 在其他数中寻找二元组，满足三数之和为0。
算法流程
①：固定一个数，cur初始化为n-1；在cur左区间初始化左右指针，left为0；right为cur-1；
②：判断左右指针指向元素之和：
a.>-固定值，right--
b.<-固定值，left++
c.=-固定值，记录，right--，left++
③：left、right相遇或交错时停止
注意：题目要求返回的三元组不重复，因此需要去重的操作：
由于数组有序，所以重复的元素一定相连，所以指针移动时跳过相同元素，即可完成去重。
tip1：三元组需要存储在vector<int>中，可以用 {a，b，c} 的形式直接赋值
tip2：由于三个正数相加肯定不为0，所以当左指针移动到正数区间时，可以结束遍历
代码
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
// 排序
sort(nums.begin(), nums.end());
// 双指针解决
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
if(nums[i] > 0) break; // ⼩优化
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
left++, right--;
// 去重操作 left 和 right
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重 i
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};8.四数之和
难度等级：⭐⭐⭐⭐
题目描述：
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
算法思路
其实四数之和与三数之和同理，只不过四数之和需要固定两个元素，再使用对向指针遍历剩余序列，三数之和时间复杂度为O(n^2)，四数之和则需要O(n^3)
算法流程
①：固定数1，ext_cur初始化为0；
②：在数1的基础上固定数2，cur初始化为 ext_cur+1；在cur右区间初始化左右指针，left 为cur+1；right为n-1；
③：判断左右指针指向元素之和：（sum=target-数1-数2）
a.>sum，right--
b.<sum，left++
c.=sum，记录，right--，left++
④：left、right相遇或交错时结束，ext_cur++重复上述操作。
注意：和三数之和一样，也需要去重，让所有指针移动时跳过重复值
代码
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
// 利⽤三数之和
for(int j = i + 1; j < n; ) // 固定数 b
{
// 双指针
int left = j + 1, right = n - 1;
long long aim = (long long)target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim) left++;
else if(sum > aim) right--;
else
{
ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
// 去重⼀
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重⼆
j++;
while(j < n && nums[j] == nums[j - 1]) j++;
}
// 去重三
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};以上就是【优选算法篇·第一章：双指针技巧】的全部内容，欢迎指正~
码文不易，还请多多关注支持，这是我持续创作的最大动力！
原文地址：https://blog.csdn.net/dhgiuyawhiudwqha/article/details/143744086
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！