双指针算法详解
一、双指针算法的核心含义
双指针是一种通过使用两个指针（索引）在数据结构（通常是数组或链表）中同时遍历的技巧。这两个指针可以：
从同一端出发，但以不同的速度移动（快慢指针）
从两端向中间移动（左右指针）
从不同位置出发，分别扫描
二、双指针算法的类型与使用技巧
1. 快慢指针
特点：两个指针从同一起点出发，但移动速度不同
应用场景：
链表中的环检测
寻找链表中点
寻找链表的第k个节点
技巧：
快指针通常移动速度为慢指针的2倍
注意边界条件处理
# 快慢指针模板
slow, fast = start, start
while fast and fast.next:
slow = slow.next # 移动一步
fast = fast.next.next # 移动两步
# 根据具体问题处理2. 左右指针（对撞指针）
特点：一个指针从起点开始，另一个从终点开始，向中间移动
应用场景：
有序数组的两数之和
反转数组
回文串判断
技巧：
通常用于已排序的数组
根据比较结果决定移动哪个指针
# 左右指针模板
left, right = 0, len(array)-1
while left < right:
if condition1:
left += 1
elif condition2:
right -= 1
else:
# 处理结果
left += 1
right -= 13. 滑动窗口
特点：两个指针维护一个窗口，根据条件动态调整窗口大小
应用场景：
子串/子数组问题
最长不重复子串
最小覆盖子串
技巧：
通常右指针扩展窗口，左指针收缩窗口
使用哈希表辅助记录窗口内状态
python
# 滑动窗口模板
left = 0
for right in range(len(array)):
# 更新窗口状态（添加right指向的元素）
while 窗口不满足条件:
# 更新窗口状态（移除left指向的元素）
left += 1
# 更新结果三、应用模板
模板1：双向遍历
def two_pointers_template1(nums):
left, right = 0, len(nums) - 1
result = []
while left < right:
# 根据条件处理
if condition(nums, left, right):
# 记录结果
result.append(...)
left += 1
right -= 1
elif nums[left] < nums[right]:
left += 1
else:
right -= 1
return result模板2：快慢指针
def two_pointers_template2(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 检测环
return True
return False模板3：滑动窗口
def sliding_window_template(s, target):
left = 0
window = {}
result = 0
for right in range(len(s)):
# 更新右边界
window[s[right]] = window.get(s[right], 0) + 1
# 收缩左边界直到满足条件
while 不满足条件(window):
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
# 更新结果
result = max(result, right - left + 1)
return result四、LeetCode实例
1. 两数之和 II（左右指针）
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # 题目要求索引从1开始
elif current_sum < target:
left += 1
else:
right -= 1
return []2. 判断链表是否有环（快慢指针）
def hasCycle(head):
if not head or not head.next:
return False
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False3. 最长无重复字符子串（滑动窗口）
def lengthOfLongestSubstring(s):
char_index = {} # 存储字符最后出现的位置
left = 0
max_length = 0
for right in range(len(s)):
if s[right] in char_index:
# 更新左指针，确保不重复
left = max(left, char_index[s[right]] + 1)
char_index[s[right]] = right
max_length = max(max_length, right - left + 1)
return max_length4. 盛最多水的容器（左右指针）
def maxArea(height):
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# 计算当前容量
width = right - left
current_height = min(height[left], height[right])
current_water = width * current_height
max_water = max(max_water, current_water)
# 移动较短的那一边
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water5. 三数之和（左右指针结合）
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # 跳过重复元素
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
result.append([nums[i], nums[left], nums[right]])
# 跳过重复元素
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < 0:
left += 1
else:
right -= 1
return result五、常见问题与优化技巧
1. 指针移动条件
明确何时移动左指针，何时移动右指针
避免死循环：确保至少有一个指针在每次迭代中移动
2. 边界条件处理
空数组或空链表
单个元素的情况
指针越界检查
3. 时间复杂度优化
双指针通常将O(n²)暴力解法优化为O(n)
结合哈希表可以进一步优化某些问题
4. 空间复杂度
多数双指针解法空间复杂度为O(1)
滑动窗口可能需要额外数据结构记录状态
六、总结
双指针是一种强大而灵活的算法技巧，特别适合处理数组和链表相关的问题。掌握不同类型的双指针模式（快慢指针、左右指针、滑动窗口）并能根据问题特点选择合适的模式，是解决许多LeetCode问题的关键。
核心要点：
识别问题是否适合双指针（通常是涉及顺序遍历、寻找特定模式或子结构的问题）
根据问题特点选择合适的指针移动策略
注意指针移动条件和边界情况
结合其他数据结构（如哈希表）可以解决更复杂的问题
双指针使用口诀与场景判断
一、核心口诀
"三看一选"口诀
一看结构：数组链表排序否？
二看目标：找位置、找范围、找关系？
三看移动：单向走、双向碰、变速跑？
一选模式：定下指针类型后开搞！
二、具体场景判断流程图
text
问题来了
↓
问自己：数据结构是什么？
↓
├─ 数组 → 是否排序？
│ ├─ 是 → 找两数/三数之和？ → 左右指针
│ ├─ 是 → 找范围/区间？ → 滑动窗口
│ └─ 否 → 需要原地修改？ → 快慢指针
│
├─ 链表 → 什么问题？
│ ├─ 环检测/找中点 → 快慢指针
│ ├─ 反转/重排 → 左右指针
│ └─ 删除节点 → 快慢指针
│
└─ 字符串 → 什么问题？
├─ 回文判断 → 左右指针
├─ 子串问题 → 滑动窗口
└─ 字符替换 → 快慢指针三、场景速查表
左右指针（对撞指针）使用场景
口诀："有序数组两头找，回文反转对对碰"
适用场景：
✅ 有序数组找两数：两数之和、三数之和、最接近的三数之和
✅ 反转类问题：反转数组、反转字符串、反转链表
✅ 回文判断：验证回文串、最长回文子串
✅ 容器盛水：盛最多水的容器
✅ 划分数组：颜色分类（荷兰国旗问题）
不适用：
❌ 无序且不能排序的数组
❌ 需要保持原始顺序的问题
快慢指针使用场景
口诀："链表环和中点，原地修改慢等快"
适用场景：
✅ 链表环问题：检测环、找环起点
✅ 链表中点：找中点、判断回文链表
✅ 原地修改：删除有序数组重复项、移动零
✅ 找倒数第N个：删除链表倒数第N个节点
✅ 数组去重：保留K个相同元素
不适用：
❌ 需要两端同时处理的问题
❌ 需要记录窗口内状态的问题
滑动窗口使用场景
口诀："子串子数组长，窗口滑动记状态"
适用场景：
✅ 子串/子数组问题：最长无重复子串、最小覆盖子串
✅ 连续区间问题：长度最小的子数组、乘积小于K的子数组
✅ 频率统计问题：找到字符串中所有字母异位词
✅ K个连续问题：最大连续1的个数 III
不适用：
❌ 不要求连续性的问题
❌ 不需要维护区间状态的问题
四、决策树 - 问自己这几个问题
问题1：需要同时从两端向中间处理吗？
是 → 左右指针
例：有序数组的两数之和
否 → 进入问题2
问题2：需要处理连续的子数组/子串吗？
是 → 滑动窗口
例：最长无重复字符子串
否 → 进入问题3
问题3：是链表问题或需要不同速度遍历吗？
是 → 快慢指针
例：链表中环检测
否 → 进入问题4
问题4：需要原地修改数组且保持相对顺序吗？
是 → 快慢指针
例：删除排序数组中的重复项
否 → 可能不适合双指针，考虑其他算法
常见模式速记
六、特别提醒与陷阱
容易混淆的场景
场景1：找"和为目标值的子数组"
如果是有序数组 → 左右指针（#167）
如果是无序数组且要求连续 → 滑动窗口（但注意：滑动窗口通常要求非负或单调）
如果是无序数组且不要求连续 → 不是双指针问题，用哈希表
场景2：删除元素
如果保持原有顺序 → 快慢指针（#27）
如果不要求顺序 → 左右指针（更高效）
场景3：字符串匹配
如果需要连续匹配 → 滑动窗口
如果只需要首尾比较 → 左右指针
七、一句话总结
"有序求和用左右，链表环中用快慢，连续子串用滑动，原地修改快慢走。"
记忆小贴士
左右指针像两个人从两头走向中间
快慢指针像龟兔赛跑
滑动窗口像摄像机在轨道上移动拍摄
最后检查清单
数据结构是否支持索引访问（数组、链表）？
是否需要同时考虑两个位置的关系？
解空间是否可以通过指针移动系统地遍历？
是否有更简单的解法？（有时哈希表更简单）
记住：双指针的核心思想是通过巧妙的指针移动减少不必要的遍历，将O(n²)优化到O(n)。当发现暴力解法中有大量重复计算时，想想能否用双指针优化！