LeetCode之双指针：算法优化利器

一、双指针算法的核心价值

双指针（Two Pointers）是算法题中高频出现的优化技巧，其本质是通过两个独立指针的协同移动，将暴力解法的O(n²)时间复杂度优化至O(n)或O(n log n)。在LeetCode题库中，双指针广泛应用于数组、链表、字符串等线性结构的处理，尤其在需要空间换时间或有序序列搜索的场景中表现突出。

1.1 算法优势分析

时间复杂度优化：将嵌套循环转化为单次遍历
空间复杂度控制：通常仅需常数级额外空间
逻辑清晰性：指针移动规则可直观描述问题解构过程
适用场景广泛：覆盖求和问题、子数组问题、链表操作等

典型案例：三数之和问题（LeetCode 15），暴力解法需O(n³)，双指针优化后降至O(n²)

二、双指针的四大经典模式

2.1 快慢指针（Fast & Slow Pointers）

核心思想：通过不同步长的指针移动解决链表环检测、中间节点查找等问题。

# 链表环检测示例
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

应用场景：

检测链表环（LeetCode 141）
查找链表中间节点（LeetCode 876）
删除倒数第N个节点（LeetCode 19）

优化要点：

快指针步长通常为慢指针的2倍
终止条件需同时判断fast和fast.next

2.2 左右指针（Left & Right Pointers）

核心思想：在有序数组中使用双向逼近策略，常见于二分查找变种和区间问题。

# 两数之和II（有序数组）
def twoSum(numbers, target):
    left, right = 0, len(numbers)-1
    while left < right:
        sum_ = numbers[left] + numbers[right]
        if sum_ == target:
            return [left+1, right+1]
        elif sum_ < target:
            left += 1
        else:
            right -= 1

典型应用：

三数之和（LeetCode 15）
最接近三数之和（LeetCode 16）
盛水最多的容器（LeetCode 11）

关键技巧：

指针移动方向由当前和与目标值的比较决定
需注意边界条件的处理（如left < right）

2.3 滑动窗口（Sliding Window）

核心思想：通过动态调整窗口大小解决子数组/子字符串问题。

# 无重复字符的最长子串
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

应用场景：

最小覆盖子串（LeetCode 76）
含有所有字符的最短子串
最大平均子数组I（LeetCode 643）

实现要点：

窗口扩张条件：满足题目要求时
窗口收缩条件：不满足要求时
使用哈希集合/字典维护窗口状态

2.4 分裂指针（Split Pointers）

核心思想：将数组分为已处理和未处理两部分，适用于原地修改问题。

# 移动零（LeetCode 283）
def moveZeroes(nums):
    non_zero = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[non_zero], nums[i] = nums[i], nums[non_zero]
            non_zero += 1

典型问题：

删除排序数组中的重复项（LeetCode 26）
合并两个有序数组（LeetCode 88）
按奇偶排序数组（LeetCode 905）

三、双指针进阶技巧

3.1 指针初始化策略

对称初始化：left=0, right=len-1（适用于有序数组）
追赶初始化：fast=slow=head（适用于链表环检测）
动态初始化：根据问题特性设置初始位置

3.2 移动规则设计

单向移动：如滑动窗口中的right指针
双向移动：如两数之和中的左右指针
条件跳跃：如跳过重复元素时的指针移动

3.3 终止条件判断

相遇条件：fast == slow（链表环）
交叉条件：left > right（数组搜索）
边界条件：right == len(nums)（滑动窗口）

四、实战案例分析

4.1 容器盛水问题（LeetCode 11）

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

优化点：

每次移动较矮的边界，因为移动较高边界不会增加面积
时间复杂度O(n)，空间复杂度O(1)

4.2 三数之和问题（LeetCode 15）

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:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 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²)

五、学习建议与常见误区

5.1 高效学习路径

从简单题目入手（如两数之和）
掌握四种基本模式
分析官方题解的指针设计逻辑
刻意练习同类题目（建议每个模式做5-10题）

5.2 常见错误及修正

指针越界：未正确处理边界条件（如left < right）
重复解问题：未跳过重复元素（需在移动指针时检查）
逻辑混乱：指针移动方向与问题要求相反（需画图辅助理解）

5.3 性能优化技巧

提前终止：当满足特定条件时可提前结束循环
剪枝策略：排除不可能的情况（如三数之和中的正数判断）
记忆化：存储中间结果减少重复计算

六、总结与展望

双指针算法作为算法优化的重要工具，其核心在于通过指针的协同移动将复杂问题分解为可控制的局部操作。在LeetCode刷题过程中，建议开发者：

建立指针移动的直觉判断
注重边界条件的处理
结合具体问题设计指针策略
通过可视化工具辅助理解

未来学习可进一步探索双指针与动态规划、贪心算法的结合应用，以及在树结构、图结构中的变种实现。掌握双指针技巧不仅有助于通过算法面试，更能培养解决实际工程问题的优化思维。

LeetCode双指针技巧全解析：从入门到精通