✨放在开头：

【从零开始的算法学习日记】系列将包含四个篇章，分别是【优选算法篇】、【递归/搜索/回溯算法篇】、【动态规划篇】以及【贪心算法篇】，每一篇章下面都会有若干章节以及数十道例题详解，博主计划在明年开春前陆续出完这些章节，欢迎大家订阅关注，敬请期待！

作为算法小白一枚，博主的初心是记录自己的学习历程，分享每一步的成长与心得。如果文章内容对你有所帮助，那将是我的荣幸。让我们一起加油，共同进步！passion！💪

 

🌈 个人主页：谁在夜里看海.

🔥 个人专栏：《C++系列》《Linux系列》《算法系列》

⛰️ 丢掉幻想，准备斗争

目录

一、算法思想

同向双指针

对向双指针

快慢双指针

二、具体运用

1.移动零

算法思路

算法流程

代码

2.复写零

算法思路

算法流程

代码

3.快乐数

算法思路

算法流程

代码

4.盛⽔最多的容器

算法思路

算法流程

代码

5.有效三⻆形的个数

算法思路

算法流程

代码

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

算法思路

算法流程

代码

7.三数之和

算法思路

算法流程

代码

8.四数之和

算法思路

算法流程

代码

---

一、算法思想

何为双指针？

双指针算法是指用两个指针来遍历数组或链表的算法技巧，一般可分为同向双指针、对向双指针以及快慢双指针。双指针算法的核心是减少时间复杂度，提高算法效率，下面会有例题进行印证。

注意：双指针算法不一定就是使用指针进行遍历，也可以通过下标等其他形式，双指针只是一个思想，并不只局限于指针。

同向双指针

两个指针从同一侧开始遍历，其中一个指针先进行移动，符合条件时，另一个指针跟上，此时两个指针会将数据划分为三块区间，前两块为处理过的区间，后一块为待处理区间：

对向双指针

两个指针分别从数组的头和尾开始向中间移动，直到它们相遇，这种方法常用于有序数组中，解决需要寻找满足特定条件的两个元素的问题，利用数组单调性，判断两个指针的移动条件。

典型例题：两数之和，如果两个指针指向的元素之和小于目标值，则移动左指针增大和；如果大于目标值，则移动右指针减小和：

快慢双指针

一个指针移动速度快，一个指针移动速度慢（一般快指针速度为慢指针的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;elsedest += 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.三数之和

难度等级：⭐⭐⭐⭐

题目链接：15. 三数之和 - 力扣（LeetCode）

题目描述：

给你一个整数数组 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.四数之和

难度等级：⭐⭐⭐⭐

题目链接：18. 四数之和 - 力扣（LeetCode）

题目描述：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、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;}};

---

以上就是【优选算法篇·第一章：双指针技巧】的全部内容，欢迎指正~ 

码文不易，还请多多关注支持，这是我持续创作的最大动力！