双指针法是一种在遍历对象时使用两个指针进行扫描的方法,通常这两个指针可以是相同方向移动(同向移动),也可以是相反方向移动(相向移动)。
常见的使用场景包括:
- 有序数组中查找两个数的和等于目标值:通过将数组排序,然后使用两个指针,一个指向数组的开头,另一个指向数组的结尾,再将两个指针相向移动,根据两指针所指元素之和与目标值的大小关系来移动指针,直到找到满足条件的两个数或者确定不存在这样的配对。
- 有序链表中查找两个数的和等于目标值:与在有序数组中的操作类似。
- 数组去重:先将数组排序,使相同的数紧挨在一起。然后定义两个指针 i 和 j,初始都指向数组起始位置,i 指针遍历整个数组,j 指针始终指向当前不重复部分的最后一个数。当 i 指针指向的元素不等于 j 指针指向的元素时,将 i 指针指向的元素复制到 j 的下一个位置,并移动 j 指针。
- 反转字符串或链表:定义两个指针分别指向字符串的头和尾(或链表的头和尾节点),然后交换两个指针所指的元素(或节点),直到两个指针相遇。
- 删除链表的倒数第 n 个节点:定义两个指针,先让一个指针(fast)向前移动 n 步,然后再同时移动两个指针(fast 和 slow),直到 fast 指针到达链表末尾,此时 slow 指针所指的就是要删除的节点的前一个节点。
- 判断链表是否存在环:使用快慢两个指针,快指针每次移动两步,慢指针每次移动一步。如果链表中存在环,快指针最终会追上慢指针;否则快指针会先到达链表尾部。
- 滑动窗口:常见于在数组或链表的某个连续区间上进行操作,例如求最长或最短子字符串、长度最小子数组等。利用循环控制窗口的终止位置,动态移动窗口的起始位置,根据窗口内数据的特征来判断和更新结果。
- 二分查找:在有序数组中查找目标元素时,可以使用左右两个指针,通过比较中间元素和目标元素的大小,来缩小查找范围,直到找到目标元素或确定其不存在。
283. 移动零【简单】
https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked
双指针法的核心思想
指针定义:
lastNonZeroIndex
: 这个指针用于跟踪下一个非零元素应放置的位置。i
: 这个指针用于遍历整个数组。
过程:
- 使用
i
指针遍历数组,检查每个元素。 - 当找到非零元素时,将其移动到
lastNonZeroIndex
指向的位置,并更新lastNonZeroIndex
。 - 在遍历完成后,使用
lastNonZeroIndex
填充剩下的位置为零。
- 使用
详细步骤
以下是对双指针法在 moveZeroes
方法中的具体应用的详细解释:
1. 初始化指针
1 | int lastNonZeroIndex = 0; |
- 初始化
lastNonZeroIndex
为0
,表示下一个非零元素应该放置在数组的起始位置。
2. 遍历数组
1 | for (int i = 0; i < nums.size(); i++) { |
- 遍历: 使用
i
从0
到nums.size() - 1
遍历每个元素。 - 条件判断:
- 如果当前元素
nums[i]
不是零,执行以下操作:- 将
nums[i]
的值赋给nums[lastNonZeroIndex]
,将非零元素移动到前面。 - 增加
lastNonZeroIndex
,为下一个非零元素腾出位置。
- 将
- 如果当前元素
3. 填充零
1 | for (int i = lastNonZeroIndex; i < nums.size(); i++) { |
- 从
lastNonZeroIndex
开始,到数组末尾,将所有剩余的位置填充为零。
示例演示
假设输入数组为 [0, 1, 0, 3, 12]
:
第一轮循环:
i = 0
:nums[0]
是零,跳过。i = 1
:nums[1]
是1
,移动到nums[0]
,更新lastNonZeroIndex
为1
。i = 2
:nums[2]
是零,跳过。i = 3
:nums[3]
是3
,移动到nums[1]
,更新lastNonZeroIndex
为2
。i = 4
:nums[4]
是12
,移动到nums[2]
,更新lastNonZeroIndex
为3
。
此时数组变为
[1, 3, 12, 3, 12]
,lastNonZeroIndex
为 `3
392. 判断子序列
双指针直接秒了,一次过!
1 | class Solution { |
5. 最长回文子串【中等】
对我来说,这题还是很有难度的,不过收获很多,由于是在刷双指针法相关的题目,所以拿到这题就在想如何用双指针做,然后,就得到了下面惨不忍睹的代码:
我的代码
1 | class Solution { |
不过这也暴露出我的一下问题:
- 对 STL 相关容器和算法不熟悉
- 多层循环逻辑不清晰
- 代码结构不清晰
总的来说,上面的代码是一坨屎。
中心扩展法
下面,欣赏一下优秀的代码:
1 | class Solution { |
在这题中,双指针主要应用在 expandAroundCenter
函数中,从基准位置向两边扩展,检查满足回文子串的条件。
具体步骤
初始化:
- 检查字符串是否为空,如果为空,直接返回空字符串。
- 初始化
start
和maxLength
,分别表示最长回文子串的起始位置和长度。
遍历字符串:
- 使用一个
for
循环遍历字符串的每个字符,以每个字符和每两个字符之间的空隙为中心,检查回文子串。
- 使用一个
检查回文子串:
- 对于每个字符
i
,调用expandAroundCenter
方法两次:- 第一次是以
i
为中心,检查奇数长度的回文子串。 - 第二次是以
i
和i+1
为中心,检查偶数长度的回文子串。
- 第一次是以
- 取这两次检查中较长的回文子串长度。
- 对于每个字符
更新最长回文子串:
- 如果当前找到的回文子串长度大于已知的最长回文子串长度,更新
start
和maxLength
。
- 如果当前找到的回文子串长度大于已知的最长回文子串长度,更新
返回结果:
- 使用
substr
方法从字符串中提取最长回文子串,并返回该子串。
- 使用