我们来详细讲解一下算法中非常常用且重要的技巧——双指针法。
这是一个概念清晰但应用极其广泛的技术，掌握它能帮助你高效解决许多问题。
一、什么是双指针法？
核心思想：顾名思义，就是在遍历对象（通常是数组或链表）时，使用两个相同方向或相反方向的指针（索引）进行扫描，通过指针的移动和相互配合来解决问题，从而避免不必要的循环，将暴力解法的时间复杂度优化到 O(n) 级别。
为什么有效？ 它通过巧妙地利用问题的内在逻辑（如有序性），避免了大量的重复计算，将复杂度从 O(n²) 降低到 O(n)。
二、双指针的三种常见类型
双指针法主要有三种常见的应用形式，我们结合例子来理解。
1. 快慢指针（前后指针）
两个指针从同一侧开始遍历，但移动速度不同（例如，一个一次走一步，一个一次走两步）。常用于链表问题。
典型问题：判断链表是否有环
• 思路：设置两个指针 slow 和 fast，起始位置都在链表头。
◦ slow 每次向后移动一个节点。
◦ fast 每次向后移动两个节点。
• 判断：
◦ 如果链表中没有环，fast 指针会先到达链表尾部（遇到 null）。
◦ 如果链表中有环，fast 指针最终会追上 slow 指针（fast == slow），就像在环形跑道上赛跑一样。
• 代码示例 (Python)
class ListNode:
def init(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
# 如果fast或fast.next为空，说明到了链表末尾，无环
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next # fast每次走两步
# 如果slow等于fast，说明有环
return True
• 其他应用：寻找链表的中间节点、寻找链表的倒数第 k 个节点。
2. 左右指针（对撞指针）
两个指针分别从序列的两端向中间移动，直到它们相遇。前提通常是序列是有序的。
典型问题：两数之和 II - 输入有序数组 (LeetCode 167)
题目：给定一个已按升序排列的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数 target。假设每个输入只对应唯一的答案，且不可以重复使用相同的元素。
• 暴力法：两层循环，时间复杂度 O(n²)。
• 双指针法：利用有序这个关键特性。
◦ 步骤：
1. 初始化：左指针 left = 0，右指针 right = len(numbers) - 1。
2. 循环条件：while left < right。
3. 计算 sum_val = numbers[left] + numbers[right]。
4. 判断：
▪ 如果 sum_val == target，找到答案，返回 [left+1, right+1] (题目要求索引从1开始)。
▪ 如果 sum_val < target，说明总和太小，需要增大。因为数组有序，所以将 left 右移（left += 1）。
▪ 如果 sum_val > target，说明总和太大，需要减小。将 right 左移（right -= 1）。
• 代码示例 (Python)
def twoSum(numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1]
elif s < target:
left += 1
else:
right -= 1
return [-1, -1] # 题目保证有解，这行不会执行
• 为什么正确？ 每次移动都排除了大量不可能的解，缩小了搜索范围。
• 其他应用：二分查找、反转字符串、三数之和、盛最多水的容器。
3. 滑动窗口（也是双指针的一种）
两个指针形成一个窗口（区间），通过移动指针的起始位置来动态地扩展或收缩这个窗口。常用于子串、子数组问题。
典型问题：长度最小的子数组 (LeetCode 209)
题目：给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
• 思路：
◦ 使用两个指针 left 和 right，代表窗口的左右边界。
◦ right 指针向右移动，扩大窗口，直到窗口内的元素总和 >= target。
◦ 一旦满足条件，记录当前窗口长度，然后 left 指针向右移动，收缩窗口，尝试寻找更小的窗口，同时更新窗口和。
◦ 重复上述过程，直到 right 到达数组末尾。
• 代码示例 (Python)
def minSubArrayLen(target: int, nums: List[int]) -> int:
left = 0
total = 0
min_len = float(‘inf’) # 初始化为一个极大值
# right指针遍历整个数组，作为窗口的右边界
for right in range(len(nums)):
total += nums[right] # 扩大窗口，加入right指向的元素
# 当窗口总和满足条件时，收缩左边界
while total >= target:
# 更新最小长度
current_len = right - left + 1
min_len = min(min_len, current_len)
# 缩小窗口，从总和里减去left指向的元素，并移动left
total -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_len
• 其他应用：字符串的排列、找到字符串中所有字母异位词、最小覆盖子串。
三、总结与要点
类型 指针方向 典型应用 关键特点
快慢指针 同向，速度不同 链表判环，找中点 常用于链表数据结构
左右指针 相向而行 有序数组的两数之和，反转数组 序列有序是关键前提
滑动窗口 同向，一前一后 最小长度子数组，字符串匹配 维护一个动态变化的区间
使用双指针法的核心要点：
- 分析问题特性：先思考暴力解法，再看数据是否有有序、单调性等特性，能否用指针移动来避免重复计算。
- 确定指针含义：明确每个指针代表什么（如链表的节点、数组的索引）。
- 确定移动规则：想清楚在什么条件下移动哪个指针，以及移动多少。
- 注意边界条件：仔细处理指针越界、相遇、初始位置等情况。
希望这个详细的讲解能帮助你彻底理解双指针法！多加练习是掌握它的最好方式。