图解 LeetCode 算法汇总——双指针

一、引言：双指针为何成为算法利器？

在LeetCode算法题库中，双指针（Two Pointers）因其高效性和简洁性，成为解决数组、链表、字符串等问题的经典技巧。其核心思想是通过两个指针的协同移动，减少不必要的遍历，将时间复杂度从O(n²)优化至O(n)。本文将通过图解与实例，系统梳理双指针的分类、应用场景及实现原理，助你高效通关算法题。

二、双指针的分类与图解

1. 快慢指针（Fast & Slow Pointers）

适用场景：链表环检测、中间节点查找、删除倒数第N个节点等。
原理：快指针每次移动两步，慢指针每次移动一步。若存在环，快指针终将追上慢指针；若无环，快指针先到达尾部。
图解示例：

链表：1→2→3→4→5→2（环起点）
快指针（F）：1→3→5→2→4→2
慢指针（S）：1→2→3→4→5→2
相遇点：2

LeetCode经典题：

• 141. 环形链表
• 876. 链表的中间节点

2. 左右指针（Left & Right Pointers）

适用场景：有序数组的两数之和、三数之和、反转字符串、滑动窗口等。
原理：左指针从起始位置开始，右指针从末尾开始，向中间移动，逐步缩小搜索范围。
图解示例（两数之和）：

数组：[2, 7, 11, 15], 目标=9
左指针（L）：0（值=2）
右指针（R）：3（值=15）
L+R=17>9 → R左移
L=0, R=2 → 2+11=13>9 → R左移
L=0, R=1 → 2+7=9 → 找到解

LeetCode经典题：

• 167. 两数之和 II - 输入有序数组
• 15. 三数之和

3. 滑动窗口（Sliding Window）

适用场景：子数组/子字符串的最大和、最小长度、无重复字符的最长子串等。
原理：通过左右指针维护一个窗口，根据条件动态调整窗口大小。
图解示例（无重复字符的最长子串）：

字符串："abcabcbb"
窗口：[a] → [ab] → [abc] → 遇到a → 左指针移至b → [bca] → ...
最大窗口：[abc] 或 [bca] 等，长度=3

LeetCode经典题：

• 3. 无重复字符的最长子串
• 209. 长度最小的子数组

三、双指针的核心优势与实现要点

1. 优势分析

• 时间复杂度优化：将嵌套循环（O(n²)）转化为单层循环（O(n)）。
• 空间复杂度降低：通常仅需常数空间（O(1)），适用于大规模数据。
• 逻辑清晰：通过指针移动规则，直观表达问题解法。

2. 实现要点

• 边界条件处理：确保指针不越界（如数组长度为0或1时直接返回）。
• 移动规则设计：根据问题需求（如相向、同向、固定步长）制定指针移动策略。
• 终止条件明确：如快慢指针相遇、左右指针交叉、窗口满足条件等。

四、实战案例：从入门到进阶

案例1：有序数组的两数之和（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)，空间O(1)。

案例2：三数之和（LeetCode 15）

问题描述：给定数组，返回所有不重复的三元组，使得a + b + c = 0。
双指针解法：

def threeSum(nums):
    nums.sort()
    res = []
    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:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                res.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
    return res

复杂度：时间O(n²)，空间O(1)（不考虑输出空间）。

五、双指针的变种与扩展

1. 链表分割（快慢指针变种）

问题：将链表分为两部分，前半部分小于x，后半部分大于等于x。
解法：使用两个虚拟头节点，分别连接小于x和大于等于x的节点，最后合并。

2. 容器盛水问题（LeetCode 11）

问题描述：给定n个非负整数表示垂直线的高度，求两条线与x轴构成的容器能盛多少水。
双指针解法：

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

原理：面积由短板和宽度决定，移动短板可能扩大面积。

六、总结与学习建议

1. 分类练习：按快慢指针、左右指针、滑动窗口分类刷题，掌握每种类型的典型问题。
2. 图解辅助：画图理解指针移动过程，避免逻辑混乱。
3. 边界意识：始终考虑空数组、单元素数组、重复元素等边界情况。
4. 代码模板：总结双指针的代码框架（如初始化、循环条件、移动规则），快速套用。

双指针是算法中的“瑞士军刀”，掌握它不仅能高效解决LeetCode问题，更能培养对问题本质的洞察力。从今天开始，用双指针解锁你的算法进阶之路吧！