我们来详细讲解一下算法中非常常用且重要的技巧——双指针法。
这是一个概念清晰但应用极其广泛的技术，掌握它能帮助你高效解决许多问题。
一、什么是双指针法？
核心思想：顾名思义，就是在遍历对象（通常是数组或链表）时，使用两个相同方向或相反方向的指针（索引）进行扫描，通过指针的移动和相互配合来解决问题，从而避免不必要的循环，将暴力解法的时间复杂度优化到 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 Falseslow = headfast = head.nextwhile slow != fast:# 如果fast或fast.next为空，说明到了链表末尾，无环if not fast or not fast.next:return Falseslow = slow.nextfast = 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 += 1else:right -= 1return [-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 + 1min_len = min(min_len, current_len)# 缩小窗口，从总和里减去left指向的元素，并移动lefttotal -= nums[left]left += 1return 0 if min_len == float('inf') else min_len
• 其他应用：字符串的排列、找到字符串中所有字母异位词、最小覆盖子串。
三、总结与要点
类型 指针方向 典型应用 关键特点
快慢指针 同向，速度不同 链表判环，找中点 常用于链表数据结构
左右指针 相向而行 有序数组的两数之和，反转数组 序列有序是关键前提
滑动窗口 同向，一前一后 最小长度子数组，字符串匹配 维护一个动态变化的区间
使用双指针法的核心要点：
- 分析问题特性：先思考暴力解法，再看数据是否有有序、单调性等特性，能否用指针移动来避免重复计算。
- 确定指针含义：明确每个指针代表什么（如链表的节点、数组的索引）。
- 确定移动规则：想清楚在什么条件下移动哪个指针，以及移动多少。
- 注意边界条件：仔细处理指针越界、相遇、初始位置等情况。
希望这个详细的讲解能帮助你彻底理解双指针法！多加练习是掌握它的最好方式。
