优选算法(双指针)

 

1.双指针介绍

双指针算法是一种常用的算法思想，特别适用于处理涉及阵列、链表或字符串等线性数据结构的问题。通过操作两个一个指针来进行导航或操作数据结构，双指针可以最大程度优化解决方案的效率。提高效率并减少空间复杂度。

在Java中使用双指针的核心思想是通过两个变量（通常是索引或节点）来标记处理数据的起点和终点，动态调整它们的位置以实现目标。

2.双指针的基本概念

• 什么是双指针？

• 双指针是指在同一个数据结构上使用双指针（通常是变量或索引）同时移动。

双指针的类型：

1.对撞指针（Two-pointer Technique）

特点

• 两个指针从数据结构的端点出发，向中间移动。
• 另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。
• 适用于集群阵列或需要从端点开始处理的线性数据结构。

应用场景

• 求和问题：在集群队列中找到两个数且相等的目标值。
• 判断回文：验证字符串是否为回文。
• 区间问题：如盛水最多的容器。

2.快慢指针（慢速指针和快指针）

特点

• 指针从同一位置开始，快两个指针的移动速度通常是慢指针的两倍。
• 常用于链表问题，快指针先走缩小范围或提前发现特定条件，慢指针才能准确定位。
• 适用于需要检测循环或寻找特定位置（如链表的中点）的场景。

应用场景

• 环检测：检测链表是否有环。
• 寻找中点：在链表中找到中间节点。
• 删除节点：删除链表中倒数第nnn一个节点。

3.滑动窗口（Sliding Window）

特点

• 两个指针用于表示一个窗口，通常是左指针left和右指针right。
• 右铰链延伸窗口，左铰链收缩窗口，直到窗口满足要求。
• 适用于动态范围问题，如求最短/最短子串。

应用场景

• 终止子串：查找无重复字符的终止子串。
• 最小覆盖子串：查找包含目标字符的最短子串。
• 子储备和问题：如找到和最大某值的最短子储备。

4.固定间隙指针（Fixed Gap Pointers）

• 定义：两个指针之间的距离固定，用于同时遍历不同的元素。

• 适用场景：

  1. 判断字符串的某种模式匹配。
  2. 滑动窗口的变体问题。

5. 双向扫描（双向扫描）

• 定义：两个指标分别从两端向中间移动，但条件可能比较复杂，不一定同时向中靠英镑。

• 适用场景：

  1. 排序索引的双指针应用。
  2. 字符串匹配问题（如跳过某些字符）。

3.题目讲解

1. 283.移动零
2. 1089. 复写零
3. 202. 快乐数
4. 11. 盛最多水的容器
5. 611. 有效三角形的个数
6. LCR 179. 查找总价格为目标值的两个商品 （原：剑指 offer：和为 s 的两个数）
7. 15. 三数之和
8. 18. 四数之和

1.移动零

1.题目解析

 从题目中我们可以了解到，只需要把数组中的0移动到最后的位置即可

2.讲解算法原理

这题我们用到快慢指针思想，我们直接定义两个指针，

fast：从左往右扫描数组，遍历数组

slow：已处理的数组区间内，非0下标的最后一个位置

示例1

-1	0	1	0	3	12
	fast
slow

我们先让fast去扫描数组中的值，当遇到0时我们不进行任何操作，让fast++，当数组中的值不为0时，我们就让slow++；

1.fast遇到0，slow不走

-1	0	1	0	3	12
		fast
slow

2.fast遇不为0时，slow++；

-1	0	1	0	3	12
		fast
	slow

3.这个时候我们将快慢指针中的两个数字进行交换

-1	1	0	0	3	12
		fast
	slow

4.换完之后我们 fast 继续走，因为num[2] = 0 ,所以slow不动

-1	1	0	0	3	12
			fast
	slow

5. fast 继续走，因为num[3] = 3 ,slow++ 并将这两个指针里的值进行交换

走完：

-1	1	0	0	3	12
				fast
		slow

 交换：

-1	1	3	0	0	12
				fast
		slow

5. fast 继续走，因为num[4] = 12 ,slow++ 并将这两个指针里的值进行交换

走完：

-1	1	3	0	0	12
					fast
			slow

 交换：

-1	1	3	12	0	0
					fast
			slow

 至此我们就全部走完了，从上面的分析我们可以得出几点：

fast从前往后便利过程中：

1.当fast没遇到0时，我们就让slow++，并交换两个指针中的值；

2.当fast遇到0时，我们就让fast++；

3.编写代码

2.复写零 

1.题目解析

 从题目中我们可以了解到，只需要把数组中的0移动到最后的位置即可

2.讲解算法原理

这题我们用到快慢指针思想，我们直接定义两个指针

如果我们按照上题的便利方法时，我们从头开始走：

当 slow 遇到0时，我们就让fast+=2，没遇到时，我们让fast++;并将fast走的数组值改为0；

示例1

数组（-1）	1	0	2	3	0	4	5	0
fast
更改后
	slow
更改后

1.

数组（-1）	1	0	2	3	0	4	5	0
	fast
更改后	1
		slow
更改后	1

2.

数组（-1）	1	0	2	3	0	4	5	0
		fast	fast
更改后	1	0	0
			slow
更改后	1	0	0	0	0	0	0

这个时候我们会发现fast将num[2] = 2 的值修改为0了，我们的slow接下来获取的值为0；那么

fast将继续走两步，并将fast走过后的值改为0，最后我们得到的值就为最后一行的内容，因此我们这样走是错的，所以我要改变思想，既然从前面行不通我们就可以想从后往前呢？

如果我们从后往前：

1.我们要确定是从后面的哪个位置开始往前便利

1.先判断 slow 位置的值
2.决定 fast 向后移动一步或者两步
3.判断一下 fast 是否已经到结束为止
4.slow++

2.处理边界情况（当最后一个位置为0时）：

我们的 fast 依然会加+=2；此时数组就越界了；所以我们要判断一下 fast 是否等于我们的数组长度；如果不等于的话，我们只需将数组改回就行，

if(fast == length) {

            arr[length - 1 ] = 0;

            slow--; fast-= 2;

}

3.“从后往前”完成复写操作

3.代码编写

3.快乐数

1.题目解析

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

 2.讲解算法原理

这题我们用到快慢指针思想，来解决检测循环或寻找特定位置（如链表的中点）的场景。

我们直接定义两个指针，

fast：快指针每次向前走两步

slow: 慢指针每次往前走一步

等他俩相遇时，判断一下值即可。

示例1：

19 ： 1^2+9^2 = 82 : 8^2+2^2 = 68 : 6^2+8^2 = 100 : 1^2+0^2+0^2 = 1;

示例2：

2 ->4->16->37->58->89->145->42->20->4->16

此时我们的示例2就为环一直循环了。

当他们为环时：我们的快指针就会先一步到达 1并开始循环1；而我们的慢指针则到达1后再开始循环1；所以当他们都为1时，就跳出循环即可。

讲解为什么这是一个无限循环：

了解：鸽巢原理，也称为抽屉原理，是组合数学中的一个基本原理。‌

该原理表明，如果有n个鸽巢和m个鸽子（m > n），那么至少有一个鸽巢中会有两个或更多的鸽子。这一原理可以推广到更一般的情况：如果有n个鸽巢和超过kn个鸽子，那么至少有一个鸽巢中有（k + 1）个鸽子。‌

因为此题的范围：

1 <= n <= 2^31 - 1

此时n的范围就为2*10^9;我们直接考虑最大值十个9的情况：

（999999999）能变的次数为 9^2*10 = 810次，于是当我们超过810次时，其中必有两个数是相同的，于是这就成环了。

3.代码编写

4.盛最多水的容器

1.题目解析

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

 2.讲解算法原理

我们从题中可以看出要取两端的最大值，并从两端的最大值中找到那个小值，乘上我们的数组长度即可，于是我们要用到的双指针思想是对撞指针来找到另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。

用法：

两个指针从数据结构的端点出发，向中间移动。

开始构思：

左边：left = 0 右边：right = 数组的长度 - 1；

0	1	2	3	4	5	6	7	8
1	8	6	2	5	4	8	3	7
left								right

我们开始向中间移动：

1： num[left] = 1 ; num[right] = 7 我们需要取得两数的最小值 来算面积 即为 1 * 8（right - left）= 8（ret）

因为我们要求最大的容积，我们就要想指针怎么移动 ，这是我们就要开始对比两边的大小了

当左边小于右边时我们就让 left++ ，反之 right--；

2： num[left] = 8 ; num[right] = 7 我们需要取得两数的最小值 来算面积 即为 7 * 7（right - left）= 49（ret）

3：num[left] = 8 ; num[right] = 3 我们需要取得两数的最小值 来算面积 即为 3 * 6（right - left）= 18（ret）

4 ……

5 ……

直到我们左边的值大于右边即停，找到其中的最大最即可：

3.代码编写

5.有效三角形的个数

1.题目解析

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 2.讲解算法原理

数学知识 ：两边之和大于第三边 即为三角形

在做之一类题时，我们都可以先对数组排序：此时我们就可利用单调性，使用双指针去解决问题；

我们要用到的双指针思想是对撞指针来找到另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。

用法：

两个指针从数据结构的端点出发，向中间移动。

开始构思：

2	2	3	4
			n-1
left		right

此时我们牵扯了三个值；

1.先固定最大的数
2.在最大的数的左区间内，使用双指针算法，"快速统计出符合要求的三元组的个数

当我们先固定完最大那个数，剩下我们只需要进行判断即可：

左边：left = 0 右边：right = i - 1；

想完上面后，我们就要想指针怎么移动了

因为数组是有序的：

1	3	4	5	6	7
					n -1
left				right

当我们遇到上面这种情况时：if（nums[left] + nums[right] < nums[n - i]）

如果我们移动right的值就会发现前面的值都比6小，因此我们只能让left++;

反之将right--；

此时这个区间内的所有数据都符合三角形，相加即可：

3.代码编写

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

1.题目解析

 购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

 2.讲解算法原理

我们看这道题时有没有发现和上题非常相似呢？

上题要我们在数组里面固定一个值，而这题我们不需要固定值了而是直接给你，所以我们举一反三可得：

我们要用到的双指针思想是对撞指针来找到另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。

用法：

两个指针从数据结构的端点出发，向中间移动。

开始构思：

左边：left = 0 右边：right = 数组的长度 - 1；

假设数据： target = 9

0	1	2	3	4	5	6	7	8
left								right

我们就要想指针怎么移动 ：

if（nums[right] + nums[left]  =  8  <( target )(9)）

如果我们移动right的值就会发现前面的值都比8小，因此我们只能让left++;

反之将right--；

如果我们满足 这两个数相加等于 target 时我们返回这组数据即可；

3.代码编写

7.三数之和

1.题目解析

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 2.讲解算法原理

我们可以看到数组中有正有负，非常不利于我们去操作数组，于是我们可以先将数组排序后

利用单调性去使用双指针去解决问题；

我们要用到的双指针思想是对撞指针来找到另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。

用法：

两个指针从数据结构的端点出发，向中间移动。

开始构思：

1.排序;
2.固定一个数 a;

• 固定一个数：通过 for 循环遍历数组的每个元素，将其固定为三元组的第一个数 nums[i]。
• 提前退出循环：如果当前数 nums[i] > 0，直接结束循环，因为排序后，nums[i] 后面的数都大于零，三数之和不可能为零。

3.在该数后面的区间内，利用“双指针算法”快速找到两个的和够于 -a 即可。

左边：left = 0 右边：right = 数组的长度 - 1；

• 双指针初始化：
  • left 指向固定数 nums[i] 的下一个元素。
  • right 指向数组的最后一个元素。
  • 目标和：target = -nums[i]，即寻找两个数的和为 -nums[i]。
• 计算双指针的和：sum = nums[left] + nums[right]。

我们就要想指针怎么移动 ：

三种情况：

1. sum > target：说明当前和太大，需要减小和，所以右指针 right-- 左移。
2. sum < target：说明当前和太小，需要增大和，所以左指针 left++ 右移。
3. sum == target：找到一个满足条件的三元组，加入结果列表 ret 中。

处理细节问题:
1.去重
找到一种结果之后，left 和 right 指针要跳过重复元素
当使用完一次双指针算法之后，i也需要跳过重复元素

避免越界

• 左指针跳过重复值：while (left < right && nums[left] == nums[left - 1]) left++。
• 右指针跳过重复值：while (left < right && nums[right] == nums[right + 1]) right--。

2.不漏
找到一种结果之后，不要"停"，缩小区间，继续寻找

3.代码编写

8.四数之和

1.题目讲解

给你一个由 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

你可以按 任意顺序 返回答案 。

 2.讲解算法原理

我们可以看到数组中有正有负，非常不利于我们去操作数组，于是我们可以先将数组排序后

利用单调性去使用双指针去解决问题；

我们要用到的双指针思想是对撞指针来找到另外根据问题要求调整其中一个指针，直到找到满足条件的结果或两个指针满足。

用法：

两个指针从数据结构的端点出发，向中间移动。

开始构思：

1.依次固定一个数 a;
2.在 a后面的区间内，利用“三数之和”找到三个数，使这三个数的和等于 target-a 即可

三数之和：1.依次固定一个数 b;
                   2.在 b 后面的区间内，利用“双指针"找到两个数使这两个数的和等于 target-a-b 即可。

目标值计算：对于当前固定的 nums[i] 和 nums[j]，目标值为 aim = (long) target - nums[i] - nums[j]。这里使用 (long) 类型转换，防止加法溢出。

双指针初始化：left 从 j + 1 开始，right 从数组末尾开始。

条件判断：

1. 如果 sum > aim，说明当前和过大，右指针 right-- 左移以减小和。
2. 如果 sum < aim，说明当前和过小，左指针 left++ 右移以增大和。
3. 如果 sum == aim，找到满足条件的四元组，加入结果列表 ret。

处理细节问题:

1.去重
找到一种结果之后，left 和 right 指针要跳过重复元素
当使用完一次双指针算法之后，i也需要跳过重复元素

避免越界

• 左指针跳过重复值：while (left < right && nums[left] == nums[left - 1]) left++。
• 右指针跳过重复值：while (left < right && nums[right] == nums[right + 1]) right--。

2.不漏
找到一种结果之后，不要"停"，缩小区间，继续寻找

3.代码编写