程序设计#4 - 【经典算法】双指针和滑动窗口·第一部分
书接上回。
滑动窗口算法是双指针算法的变形，而且因为入门门槛低，我打算下一期就做这个了。
双指针算法（two-pointer algorithm）是处理序列（如数组、链表、字符串）的强大技巧。它通过维护两个指针（索引）来追踪序列中的某个范围或元素，从而高效地解决问题。
它尤其擅长解决子数组或子串的相关问题（特别是滑动窗口）。子数组就是一个完整数组里连续的一段，子串就是字符串里连续的一段。
对于输入所给的序列，尽管它们具有确定的顺序，但我们对它一无所知。除非使用索引 arr[i] 查询，否则永远也不可能一次性知道所有元素的位置。
这时候，如果我们身处一个序列中，就像是在一条漆黑的走廊里。运用暴力算法就像是一次只打开一盏灯，看当前位置的元素，然后穷举所有的可能结果。这样做的最坏时间复杂度可能超过 O(n2)。
换一个思路，通过移动两个指针来动态维护一个区间或追踪两个元素。在移动过程中，根据当前区间的信息，我们可以智能地排除许多无效的候选解，从而避免暴力枚举，将时间复杂度优化到 O(n) 或 O(n log n)。
这就叫做双指针1算法。
打个比方，在黑暗的走廊中一个人找答案当然是很慢的，所以我们派出两名干员，拿着手电筒搜索，他们速度一快一慢，或者左右相向而行。这样，通过两名探员的左右协同，就实现了快速定位或是缩小范围的目的。而又因为我们对两名探员的位置是时刻掌握的，所以同时也能求出这个范围的大小。所以，这样就能很快地找到答案。
另外，利用快慢指针的特点，我们能快速地判断一个未知长度的序列（通常是链表）的中点位置。
滑动窗口是双指针的变形，它的本质就是把两个指针作为窗口的左端点和右端点。这就好比在走廊里打开了一盏可调节宽度的探照灯，并且在序列中平滑地移动，这样也能高效地寻找最优解。
双指针基础应用
新手教程 - intro
上面已经写到，两个指针通常一快一慢（也叫快慢指针或同向指针），或是相向而行（对撞指针）。我们通过两个例题体会一下。
给你一个数组
nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设
nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。- 返回
k。
如果这一题不用原地修改，那么只需要简单地开一个新数组就可以了。
但是这里不行。所以考虑用一个快指针遍历整个数组，当快指针遍历到 val 时就跳过，否则就将此时的值传递给 nums[slow]，接着 slow++。
定义两个关键变量 slow 和 fast：
slow指向下一个可以被写入新元素的位置。slow的值也代表了函数处理后有效数组的长度。它从0开始。fast用于查看数组的全部元素。
然后需要写 slow 前进的条件：
if nums[fast] != val {
// ...
}这行代码就是在说：当前的元素不是 val，应该被保留。
结合一下，就能得到下面的代码。
func removeElement(nums []int, val int) int {
var slow int
for fast := range nums {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
}
return slow
}我在之前就写过解法，直接粘贴过来即可。
func reverseString(s []byte) {
l := 0
r := len(s) - 1
// 两个指针碰头时，就代表他们抵达了中点
// 这时候跳出循环，字符串就完成了反转
for l < r {
s[l], s[r] = s[r], s[l] // a, b = b, a 表示交换 a 和 b 的值
l++
r--
}
}这一段代码并不难理解。事实上就是把第一位跟最后一位交换，把第二位跟倒数第二位交换……直到两个指针在中间碰头，整个字符串也就完成了交换。
快慢指针 - 变形
数组去重问题 - 忽略重复项
上面看的都是一些简单而且特殊的情形，现在我们把快慢指针（fast-slow pointers）的用法往下推广。
例如上面 leco27 的第一种变形：26. 删除有序数组中的重复项 - 力扣（LeetCode）
这题跟 leco27 的共通点在于，需要考查快指针遍历到的元素是否符合不重复的条件。
为了寻找普遍性，这里我们改为实现一个 RmDup() 函数。这个函数接受两个输入：数组 nums 以及最大重复次数 k。因为数组已经排好序，所以相同的元素一定是相邻的。所以与 leco27 相同，快慢指针分别代表：
- 快指针
fast遍历整个数组 - 慢指针
slow标记新数组的写入位置
先从 k == 1 的情形开始。
第一步·确定范围。假设 nums[i] == nums[i-1]（不超出索引范围），那么我们就知道，从 nums[i-1] 到 nums[i] 都是相同的数字，一共是 2 个。
接着，如果 nums[i] == nums[i-k]，从 nums[i-k] 到 nums[i] 都是相同的数字，一共是 k+1 个
所以，在上面的这种情况下，只要停留在一组相同数字的第 k+1 位，就能实现保留 k 位的效果。
第二步·考查元素。这就涉及到整个算法的核心逻辑。
位置
slow-k到slow-1正好是最近写入的 k 个元素。slow-k就是从当前写入位置向前数第 k 个元素。如果这 k 个元素都与
nums[fast]相同，说明当前元素已经达到重复上限。有效数组: [x, x, ..., nums[slow-k], ..., nums[slow-1]] 索引: 0, 1, ..., slow-k, ..., slow-1 长度: <------- slow 个元素 ------->这种方法的巧妙之处在于：不需要维护复杂的计数器，只需要利用有序数组的特性和简单的指针运算就能判断重复次数。
如果当前考查的元素 nums[fast] 不等于 nums[slow-k]，就说明这个元素应该被保留，将它放到 slow 的位置上。
这也意味着，我们只需要把 slow 的值初始化为 k，因为在索引 k 以前的元素必定没有重复超过 k 次
这样做的原因是，如果
nums[slow-k] == nums[fast]，意味着保留的元素超过了 k 位，所以忽略。
假设 k == 2，数组为 [1, 1, 1, 2, 2, 3, 4, 4, 4]。
nums: [1, 1, 1, 2, 2, 3, 4, 4, 4]
index: 0 1 2 3 4 5 6 7 8| 步骤数 | fast | slow | nums[slow-k] | nums[fast] | 是否保留 |
|---|---|---|---|---|---|
| 0（初始化） | - | 2 | - | - | 保留前 2 个 |
| 1 | 2 | 2 | nums[0] == 1 | nums[2] == 1 | ❌ |
| 2 | 3 | 2 | nums[0] == 1 | nums[3] == 2 | ✅ |
| 3 | 4 | 3 | nums[1] == 1 | nums[4] == 2 | ✅ |
| 4 | 5 | 4 | nums[2] == 2 | nums[5] == 3 | ✅ |
| 5 | 6 | 5 | nums[3] == 2 | nums[6] == 4 | ✅ |
| 6 | 7 | 6 | nums[4] == 32 | nums[7] == 4 | ✅ |
| 7 | 8 | 7 | nums[5] == 4 | nums[8] == 4 | ❌ |
于是处理完的数组就变成了:
nums: [1, 1, 2, 2, 3, 4, 4]
index: 0 1 2 3 4 5 6具体实现代码如下。注意特判数组长度小于 k 的情况。
func removeDuplicates(nums []int) int {
return RmDup(nums, 1)
}
func RmDup(nums []int, k int) int {
if len(nums) < k { // 特判
return len(nums)
}
slow := k
for fast := k; fast < len(nums); fast++ {
if nums[slow-k] != nums[fast] { // 关键代码，直接决定了是否保留 nums[fast]
nums[slow] = nums[fast]
slow++
}
}
return slow
}这个算法其实是有局限性的。如果要处理的是一个二维数组，这个算法就束手无策了。而且对于未排序数组，这个算法无效。但我们在此处其实是为了讲明白双指针的用法，改进方案现在不需要考虑。
这道题将 k 改为 2 就是 80. 删除有序数组中的重复项 II - 力扣（LeetCode），只要这样改即可。
func removeDuplicates(nums []int) int {
return RmDup(nums, 2)
}
// 其余不变链表问题 - 链表中点
快慢指针还有一个特点：如果当两个指针的运动速度恒定，那我们能够很方便地找出一个序列中的第 1/n 位，其中 n 是快指针速度除以慢指针速度的结果。
这在链表这种长度未知的序列中非常奏效。比如 876. 链表的中间结点 - 力扣（LeetCode）。
链表快速入门：
链表（这里指无环单向链表，singly-linked list）由若干个结点组成，其中每个结点有一个值，而且有一个指向下一个结点的指针（叫做后继指针，常用结构体指针实现）。
只要知道了链表的第一个结点，就能顺序推出链表的所有结点。反过来则不行，但双向链表可以。
链表是可以有环的。环链表的最后一个节点的后继指针指向链表中的某个节点，形成一个闭环，而不是像无环链表一样指向空指针。
双向链表的结点除了指向有下一个结点的指针，也有指向上一个结点的指针（叫做前驱指针），所以此时只要知道双向链表的任意一个结点就能推出链表的所有节点。
特别地，循环链表的最后一个结点指向头结点，从而形成一个闭环。
下面是一个实现单向链表结点的结构体代码。
type ListNode struct { Data int // 当前结点的值 Next *ListNote // 后继指针，指向另一个结点结构体 }
因为需要找的是链表的中点（二分之一位置），所以让快指针走两步时，慢指针只走一步。
/**
* 单向链表的定义如下
* type ListNode struct {
* Val int
* Next *ListNode
* }
* 如果不加声明，默认单向链表定义都如此
*/
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil { // 判定空指针，而且不能颠倒，原因看下面
fast = fast.Next.Next
slow = slow.Next
}
return slow
}原题中输入的链表结点是一个结构体指针，是指针就必须要考虑空指针的情况。
因为 && 运算符会先判断前面的值是否为 true（判定结果如果是 false 就不用判定后面的值了），所以应该先判断 fast 是否为一个空指针。否则当 fast 是一个空指针时，先判断 fast.Next 会导致程序 panic。
链表问题 - 链表中环的起点和长度
快慢指针的速度差还能帮助解决判定链表是否有环的问题。
假如有一个跑道，事先不知道这个跑道是环形跑道还是直线型跑道，两名同学一快一慢从起点开始跑。如果最终快的同学赶上了慢的同学，说明跑道是有环的；否则，如果快的同学跑到了终点（fast == nil 或 fast.Next == nil）都没追上慢的同学，说明跑道是直线型的。
不难理解，所以直接写出如下的代码。
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil { // 判定是否走到了链表末尾结点
slow = slow.Next
fast = fast.Next.Next
if slow == fast { // 快指针追上了
return true
}
}
return false
}这只能告诉我们链表是否有环。那么我们就来试试看分析两个指针和链表是否有一些有趣的性质，让我们能找到环的起点跟环的长度。
数学推导：
设
slow走过路径长为 ，那么fast走过的路径长为 ．如下图所示，将链表抽象为如下所示的图形．设链表的头为点 ，环的起点为点 ，两指针相遇点为点 ．
链表 令 环的长度为 ，且取两自然数（不是任取） ．显然对于 ，有
两者作差，即
也就是说
slow走过的距离恰好是环长度的整数倍．因为无论走了多少圈，slow最终都在点 上，因此slow可视作从点 开始走了一整圈，回到点 ．所以有就是所求的环的起始位置．
容易想到，将快指针
fast复位到点 ，接着将fast与slow的速度同时调至每次前进一步．此时只要
fast == slow，此时的slow就是环的起点．
上面的推导过程转换为代码，如下所示。
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for {
if fast == nil || fast.Next == nil { // 将判断空指针移动到循环内
return nil
}
fast = fast.Next.Next
slow = slow.Next
// 两指针碰头，说明链表有环
if fast == slow {
// fast 回复到链表头，重新开始遍历
fast = head
break
}
}
for {
if fast == slow {
break
}
slow = slow.Next
fast = fast.Next // 两者速度调整到每次前进一步
}
return slow // 找到起点
}这就是142. 环形链表 II - 力扣（LeetCode）的解法。
如果要求环的长度，只要把 slow 按住不动，fast 前进直到再次碰头即可。方法雷同所以不再展示代码。事实上这种找链表环的方法叫做弗洛伊德判圈法，它是一种基于数学归纳法和基本事实的判圈方法。
对撞指针 - 变形
二分查找 - 对撞指针特例
事实上在复杂度那时候我们就见过对撞指针（collision pointer）了，不过那时候它还不叫对撞指针，而是叫做二分查找。
二分查找就是对撞指针的特例之一。它通过不断减半左右指针框住的范围大小，从而实现在 O(log n) 的时间复杂度以内，在有序数组里搜索（search）特定元素。
func peakIndexInMountainArray(arr []int) int {
var left, mid int
right := len(arr) - 1
for right > left {
mid = (right + left) / 2 // 找中点
if arr[mid] < arr[mid+1] { // 判断峰值方向
// 为真，山顶在 mid 右侧
left = mid + 1
} else {
// 为假，山顶在 mid 左侧
right = mid
}
}
return left
}在上面的代码中，left 和 right 最终会撞在一起，此时也就找到了山顶。
二分查找虽然快，但是它只能针对已经以特定顺序排好的数组进行搜索，否则就是白忙活。
对撞指针也是一样，必须在排好序的数组里，它才能发挥作用。
因为排好序的数组具有单调性，单调性能给指针移动提供依据，因此这种单调性是双指针搜索不可或缺的。
寻找双元组 - 有序数组内的对撞指针
leco1 两数之和给出的哈希表解法事实上适用于所有同类问题，但是如果放在 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）里面，我们会发现空间复杂度跟 leco1 相差无几，这显然不合理。
再往下看，leco1 的数组是无序的，但 leco167 的数组已经预先排好序（非递减顺序）。我们没有用上排好序这个性质，所以才会导致较劣的空间复杂度。
上面已经说过，对撞指针非常适合应用在排好序的数组中，我们就分析一下，利用排好序，能不能优化复杂度。
给你一个下标从 1 开始的整数数组
numbers，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]，则1 <= index1 < index2 <= numbers.length。以长度为 2 的整数数组
[index1, index2]的形式返回这两个整数的下标index1和index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
假设当前将指针摆在第一位和最后一位，给出一个 now 记录当前的和，也就是 now = numbers[left] + nunbers[right]。
因为数组已经排好了序，所以
- 要使
now增大，必须将左指针右移（增大较小的数） - 要使
now减小，必须将右指针左移（减小较大的数）
因此很容易根据上面的条件写出流程控制。直到 now == target 即可返回。
⚠️注意：对撞指针事实上仍然是两个指针，因此在原题中明确提到不能重复使用元素的前提下，不能让左右指针重合。
// 错误示范
if now <= target {
left++
}将上面的过程画成图，如下所示。
初始值
numbers: [2, 7, 11, 15]
target: 9
初始状态: left=0, right=3
numbers: [2, 7, 11, 15]
↑ ↑
left right
第 1 轮: 2 + 15 = 17 > 9 → 太大，right--
numbers: [2, 7, 11, 15]
↑ ↑
left right
第 2 轮: 2 + 11 = 13 > 9 → 太大，right--
numbers: [2, 7, 11, 15]
↑ ↑
left right
第 3 轮: 2 + 7 = 9 == 9 → 找到答案！
返回值: [left+1, right+1] == [1, 2]注意题目中的下标不是我们常见的 0-based 下标（索引从 0 开始）而是 1-based 下标，因此处理完要给两指针加上 1。
func twoSum(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
// 指针开始运动
for left < right {
now := numbers[left]+numbers[right]
if now == target { // 满足条件
return []int{left+1, right+1}
} else if now < target { // 比 target 小，左指针右移
left++
} else {
right--
}
}
return []int{}
}寻找三元组 - 对撞指针高阶
然后我们突然发现 Go 内置了 sort 包用于调用排序函数。所以我们甚至能够把双指针算法推广到更复杂的情况中。
例如 leco15 三数之和。它输入的数组没有排序，我们就能够先调用 sort.Ints()，将复杂的三元组问题转化为简单的双指针问题。
想一想为什么数组要先排序？
我们先在数组中取一个固定点 i。这个 i 的相反数 -i 事实上就是 leco167 中的 target ，意思就是，我们要在数组中找到两个数 nums[left] 和 nums[right] ，使得 -nums[i] == nums[left] + nums[right]。
观察三元组的特点，我们能得到 i 在区间 [0, len(nums)-3] 中。也就是说，我们的目标转换成了解决 len(nums)-3 次两数之和问题。
整个程序的流程如下。
- 给数组排序：
sort.Ints(nums) - 对于每个索引
i：- 跳过重复值。如果
i > 0且nums[i] == nums[i-1]，跳过当前i - 设置目标。
target = -nums[i] - 初始化对撞指针。
left = i + 1，right = n - 1（左指针初始化为i+1的原因是避免跟i重复，但下面还有去重） - 对向指针搜索：
- 当
left < right：- 计算
sum = nums[left] + nums[right] - 如果
sum == target：找到解，记录三元组- 去重处理：跳过所有重复的
nums[left]和nums[right]
- 去重处理：跳过所有重复的
- 如果
sum < target➡️left++ - 如果
sum > target➡️right--
- 计算
- 当
- 跳过重复值。如果
- 返回所有三元组。
可视化处理如下。
排序：
原数组: [-1, 0, 1, 2, -1, -4]
排序后：
nums = [-4, -1, -1, 0, 1, 2]第一轮：
i = -4
target = 4
nums: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
i left right
-1 + 2 = 1 < 4 → left++
-1 + 2 = 1 < 4 → left++
0 + 2 = 2 < 4 → left++
1 + 2 = 3 < 4 → left++ (left >= right，结束)
本轮未找到符合条件的三元组第二轮：
i = -1
target = 1
nums: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
i left right
-1 + 2 = 1 == 1 → 找到解 [-1, -1, 2]
去重：移动left和right跳过重复值
然后 left++，right--继续搜索：
数组: [-4, -1, -1, 0, 1, 2]
↑ ↑ ↑
i left right
0 + 1 = 1 == 1 → 找到解 [-1, 0, 1]
本轮找到 1 个三元组 [-1, -1, 2] [-1, 0, 1]转换成代码如下所示。
func threeSum(nums []int) [][]int {
sort.Ints(nums) // 排序
res := [][]int{}
n := len(nums)
for i := range n - 2 { // 在区间 [0, n-3] 内寻找 i
// 去掉重复的 nums[i]
// 这一行是最关键的！直接决定去重是否彻底
if i > 0 && nums[i] == nums[i-1] {
continue
}
// 数组是已经排好序的，因此假如 i == 0，无论如何都找不到符合条件的三元组
if nums[i] > 0 {
break
}
// 开始对撞指针
left, right := i+1, n-1
target := -nums[i] // 与 leco167 一致，先定下 target
for left < right { // 指针撞上
now := nums[left] + nums[right]
if now == target { // 找到了三元组，加入答案中
res = append(res, []int{nums[i], nums[left], nums[right]})
//下面两个循环都是为了去除重复的 nums[left] 和 nums[right]
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
// 到了这里，说明 nums[left] 和 nums[right] 都停在重复的最后一位
left++
right--
// 如果去重安排在记录解之前，会造成漏解
} else if now < target { // 下方处理同 leco167
left++
} else {
right--
}
}
}
return res
}这个算法的时间复杂度也很有意思。首先 sort.Ints() 看作调用快速排序，所以它的时间复杂度是 O(n log n)。
下面虽然嵌套三层循环，但是最里面一层的循环是为了去重，只有外面两层循环会遍历数组。所以这个三层循环的时间复杂度是 O(n^2)
运用渐进分析，当 n 很大时（本题中为 1,000），实际上的时间复杂度是 O(n^2)。
如果使用单纯的三层循环遍历，那么时间复杂度会恶化到 O(n^3)。我们在上面写的算法是显然更优的。
空间复杂度主要看排序算法。因为是快速排序，空间复杂度就是 O(1)。
上面的 固定数 -> 对撞指针（有时也叫固定指针+对向双指针的三指针模式）可以看做一种双指针思想，leco16 最接近的三数之和、leco18 四数之和也可以用这种思想解决。它们的解法放在本文的额外部分。
⚠️注意：在寻找元组问题中，去重是这一类题的最大难点。必须在找到一组解后，跳过所有相同的左指针值和右指针值。同时，固定的那个数也需要去重。
额外部分
leco16 最接近的三数之和 解法
func threeSumClosest(nums []int, target int) int {
var res int
abs := 2147483647 // impossible
sort.Ints(nums)
fmt.Println(nums)
n := len(nums)
for i := range n - 2 {
if i > 0 && nums[i] == nums[i-1] { // 去掉重复的 i
continue
}
left, right := i+1, n-1
for left < right {
now := nums[i] + nums[left] + nums[right]
if now == target {
return target
} else if now < target {
if abs > target-now {
abs = target - now
res = now
}
left++
} else {
if abs > now-target {
abs = now - target
res = now
}
right--
}
}
}
return res
}leco18 四数之和 解法
func fourSum(nums []int, target int) [][]int {
if len(nums) < 4 {
return [][]int{}
}
res := [][]int{}
n := len(nums)
sort.Ints(nums)
for i := range n - 3 {
if i > 0 && nums[i] == nums[i-1] { // 去重
continue
}
if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target { // 第一组优化
break
}
if nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target { // 第二组优化
continue
}
for j := i + 1; j < n-2; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
if nums[j]+nums[j+1]+nums[j+2]+nums[i] > target { // 第一组优化
break
}
if nums[j]+nums[n-1]+nums[n-2]+nums[i] < target { // 第二组优化
continue
}
left, right := j+1, n-1
for left < right {
now := nums[j] + nums[left] + nums[right] + nums[i]
if now == target {
res = append(res, []int{nums[j], nums[left], nums[right], nums[i]})
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if now < target {
left++
} else {
right--
}
}
}
}
return res
}这其实就是 leco15 三数之和 多套了一层循环。因为方法类似就不再解释循环的用途，但其中有两个优化的点。
下面两个优化可以放在三数之和的解法中。
第一组优化
if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target { // 第一组优化
break
}if nums[j]+nums[j+1]+nums[j+2]+nums[i] > target { // 第一组优化
break
}如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target，这就说明此时的 i 已经太大了，在这之后无论怎么找都不会找到等于 target 的四数之和。（因为此时 nums[i+1]、nums[i+2] 和 nums[i+3] 已经是 nums[i] 之后的三个最小值）
下面在 j 的循环里也是一样。
第二组优化
if nums[i]+nums[n-1]+nums[n-2]+nums[n-3] < target { // 第二组优化
continue
}if nums[j]+nums[n-1]+nums[n-2]+nums[i] < target { // 第二组优化
continue
}如果 nums[j]+nums[n-1]+nums[n-2]+nums[i] < target，就说明此时的 i 太小了，直接跳过进入下一次循环即可。（因为 nums[n-1]、nums[n-2] 和 nums[i] 已经是整个数组里三个最大的数了）
在双指针和滑动窗口的第一部分，我们讨论了双指针两种最最基础的应用：快慢指针和对撞指针。
快慢指针可以用来解决去除数组内重复项的问题，也可以用来寻找链表等未知长度序列的中点以及链表环。而对撞指针适合在排好序的数组内寻找和一定的元组，对撞指针只遍历了一次数组，所以对撞指针的时间复杂度是 O(n)，远远优于暴力两次遍历的 O(n^2)。
以上就是 【经典算法】双指针和滑动窗口·第一部分 的全部内容。下一期将会讲解双指针的一个经典变形：滑动窗口。接着就是双指针的特殊应用（荷兰国旗问题，三指针算法）。
🎉撒花🎉