图解双指针：LeetCode 算法高效解题指南

一、双指针算法概述

双指针（Two Pointers）是算法竞赛和面试中高频出现的技巧，其核心思想是通过维护两个或多个指针的移动关系，将时间复杂度从暴力解法的O(n²)优化至O(n)或O(log n)。在LeetCode中，双指针广泛应用于数组、链表、字符串等线性结构的操作，尤其适合处理需要同时遍历或比较多个位置的场景。

1.1 双指针的分类

双指针根据移动方式可分为三类：

• 同向移动：两个指针均从左向右移动，但速度不同（如快慢指针）。
• 相向移动：两个指针分别从数组两端向中间移动（如双端查找）。
• 固定间距移动：两个指针保持固定距离，同步移动（如滑动窗口）。

1.2 适用场景

双指针的典型应用场景包括：

• 数组/链表中的子序列问题（如最长无重复字符子串）。
• 排序数组中的两数之和、三数之和。
• 链表中的环检测、倒数第K个节点。
• 字符串匹配与回文判断。

二、同向双指针：快慢指针详解

快慢指针是同向双指针的代表，常用于链表和数组的边界问题。

2.1 链表环检测（LeetCode 141）

问题描述：判断链表是否有环。
快慢指针解法：

• 慢指针每次移动1步，快指针每次移动2步。
• 若存在环，快慢指针终将相遇；若无环，快指针先到达尾部。

代码实现：

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

图解分析：

• 初始时，快慢指针均指向头节点。
• 每次迭代，快指针比慢指针多走1步，若存在环，两者距离逐渐缩小至0。

2.2 链表中间节点（LeetCode 876）

问题描述：找到链表的中间节点。
快慢指针解法：

• 慢指针每次移动1步，快指针每次移动2步。
• 当快指针到达尾部时，慢指针指向中间节点。

代码实现：

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

优化点：

• 若链表长度为偶数，此方法返回第二个中间节点（如长度为4时返回第3个节点）。

三、相向双指针：双端查找技巧

相向双指针通过从两端向中间移动，高效解决排序数组中的区间问题。

3.1 两数之和 II（LeetCode 167）

问题描述：在已排序数组中找到两数之和等于目标值的索引。
双指针解法：

• 初始化左指针在起始位置，右指针在末尾位置。
• 计算两指针指向元素的和：
  • 若和等于目标值，返回索引。
  • 若和小于目标值，左指针右移以增大和。
  • 若和大于目标值，右指针左移以减小和。

代码实现：

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-based索引
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]  # 未找到

时间复杂度：O(n)，仅需一次遍历。

3.2 盛水最多的容器（LeetCode 11）

问题描述：在高度数组中，找到两条线与x轴形成的容器能盛最多水。
双指针解法：

• 初始化左指针在起始位置，右指针在末尾位置。
• 计算当前容器面积：min(height[left], height[right]) * (right - left)。
• 移动高度较小的指针（因为面积受限于较短边）。

代码实现：

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        current_area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, current_area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

贪心策略：每次移动可能增加面积的指针（即较短边）。

四、滑动窗口：固定间距双指针

滑动窗口通过维护一个可变大小的窗口，解决子序列或子数组问题。

4.1 无重复字符的最长子串（LeetCode 3）

问题描述：找到字符串中最长的无重复字符子串。
滑动窗口解法：

• 使用哈希集合记录窗口内的字符。
• 右指针扩展窗口，若遇到重复字符，左指针收缩窗口。

代码实现：

def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

复杂度分析：O(n)，每个字符最多被访问两次。

4.2 最小覆盖子串（LeetCode 76）

问题描述：在字符串S中找到包含字符串T所有字符的最小子串。
滑动窗口解法：

• 使用哈希表记录T的字符频率。
• 扩展右指针直到窗口包含T所有字符。
• 收缩左指针以寻找更小的满足条件的窗口。

代码实现：

from collections import Counter
def minWindow(s, t):
    t_count = Counter(t)
    required = len(t_count)
    formed = 0
    window_counts = {}
    left, right = 0, 0
    ans = float("inf"), None, None
    while right < len(s):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        if char in t_count and window_counts[char] == t_count[char]:
            formed += 1
        while left <= right and formed == required:
            char = s[left]
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            window_counts[char] -= 1
            if char in t_count and window_counts[char] < t_count[char]:
                formed -= 1
            left += 1
        right += 1
    return "" if ans[0] == float("inf") else s[ans[1]:ans[2]+1]

关键点：

• formed变量跟踪当前窗口是否满足条件。
• 仅在formed == required时尝试收缩窗口。

五、双指针的实战建议

1. 画图辅助：对复杂问题，先手动模拟指针移动过程。
2. 边界处理：注意空数组、单元素数组等特殊情况。
3. 模板化思维：
   • 同向指针：初始化slow = fast = head，快指针先移动。
   • 相向指针：初始化left = 0, right = len(arr)-1，根据和/差调整指针。
   • 滑动窗口：初始化left = 0，右指针遍历，内层循环收缩左指针。
4. 变种问题：如三指针（LeetCode 15. 三数之和）可通过固定一个指针，转化为双指针问题。

六、总结

双指针是LeetCode算法中的“瑞士军刀”，其高效性源于对线性结构的深度利用。通过掌握同向、相向和滑动窗口三种模式，可解决80%以上的指针类问题。建议读者结合本文图解与代码实现，在LeetCode中针对性练习（如数组、链表、字符串标签下的双指针题目），逐步培养指针移动的直觉。