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

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

双指针（Two Pointers）是解决数组、链表、字符串等线性结构问题的经典算法范式，其核心思想是通过维护两个或多个指针的协同移动，将时间复杂度从暴力解法的O(n²)优化至O(n)或O(log n)。在LeetCode中，双指针技术广泛应用于以下场景：

有序数组的配对问题：如两数之和、三数之和
链表操作：环检测、倒数第K个节点、合并有序链表
滑动窗口问题：最长无重复字符子串、最小覆盖子串
字符串匹配：回文串验证、字符串压缩

以LeetCode 167题《两数之和 II - 输入有序数组》为例，暴力解法需双重循环遍历，时间复杂度O(n²)。而双指针解法通过头尾指针向内收缩，仅需O(n)时间：

def twoSum(numbers, target):
    left, right = 0, len(numbers)-1
    while left < right:
        sum_val = numbers[left] + numbers[right]
        if sum_val == target:
            return [left+1, right+1]
        elif sum_val < target:
            left += 1
        else:
            right -= 1

二、双指针的四大变种模式

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

典型应用：链表环检测（LeetCode 141）、中间节点查找（LeetCode 876）
原理：快指针每次移动两步，慢指针移动一步，若存在环则必相遇。时间复杂度O(n)，空间复杂度O(1)。

# 链表环检测实现
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

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

典型应用：有序数组两数之和（LeetCode 167）、三数之和（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

3. 滑动窗口（Sliding Window）

典型应用：最长无重复子串（LeetCode 3）、最小覆盖子串（LeetCode 76）
实现要点：维护一个可变大小的窗口，通过哈希表记录字符频率，动态调整窗口边界：

# 最长无重复子串实现
def lengthOfLongestSubstring(s):
    char_map = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)  # 更新左边界
        char_map[s[right]] = right
        max_len = max(max_len, right - left + 1)
    return max_len

4. 分离指针（Split Pointers）

典型应用：合并两个有序数组（LeetCode 88）、平方数排序（LeetCode 977）
技巧：利用数组有序特性，从后向前填充结果数组，避免额外空间开销：

# 合并两个有序数组（nums1长度为m+n，后n个元素为0）
def merge(nums1, m, nums2, n):
    p1, p2, p = m-1, n-1, m+n-1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    nums1[:p2+1] = nums2[:p2+1]  # 处理nums2剩余元素

三、双指针的优化策略

边界条件处理：特别注意空数组、单元素数组、重复元素等边界情况
指针移动规则：明确每次循环后指针的移动方向和条件
空间复杂度优化：通过原地修改（如链表反转）减少额外空间
提前终止条件：如找到目标值后立即返回，避免无效遍历

四、实战建议

画图辅助：复杂问题（如链表环检测）建议先画指针移动轨迹
模板化思维：总结常见问题的双指针模板（如滑动窗口的初始化和边界调整）
对比学习：对比双指针解法与暴力解法的时间复杂度差异
刻意练习：从简单题（如两数之和）入手，逐步挑战中等难度题（如三数之和）

五、经典题目推荐

难度	题目编号	题目名称	核心技巧
简单	167	两数之和 II	左右指针
中等	15	三数之和	左右指针+去重
中等	142	环形链表 II	快慢指针+数学推导
中等	76	最小覆盖子串	滑动窗口+哈希表
困难	42	接雨水	双指针+动态规划

双指针算法的本质是通过空间换时间或智能移动策略减少不必要的计算。掌握其核心思想后，可灵活应用于字符串处理、数组操作、链表遍历等多种场景。建议开发者通过LeetCode分类标签系统，针对性练习双指针相关题目，逐步提升算法设计能力。

LeetCode 双指针技巧全解析：从基础到进阶的实战指南