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

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

双指针技术是解决数组、链表、字符串等线性结构问题的核心算法之一，其本质是通过维护两个或多个指针的移动关系，将O(n²)的暴力解法优化为O(n)或O(log n)的线性复杂度。在LeetCode算法题中，双指针的应用场景涵盖：

1. 有序数组的二分搜索：通过左右指针收缩搜索范围
2. 链表环检测：快慢指针的相对运动揭示环结构
3. 滑动窗口问题：动态调整窗口边界的指针操作
4. 三数/四数之和：左右指针配合去重与剪枝

典型案例：LeetCode第141题「环形链表」中，快指针每次移动两步，慢指针每次移动一步，若存在环则两指针必相遇。这种时空复杂度均为O(n)的解法，相比哈希表存储节点（O(n)空间）具有显著优势。

二、双指针的四大类型与实现要点

1. 快慢指针（龟兔赛跑）

应用场景：链表环检测、中间节点查找、删除倒数第N个节点
实现技巧：

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

关键点：快指针步长是慢指针的两倍，终止条件需同时判断fast和fast.next是否为空。

2. 左右指针（对撞指针）

应用场景：有序数组两数之和、三数之和、容器盛水问题
实现技巧：

# 两数之和II示例
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

关键点：指针移动方向相反，需注意边界条件left < right的判断。

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

关键点：右指针扩展窗口，左指针在重复时收缩，需维护窗口内元素的唯一性。

4. 分裂指针（头尾分离）

应用场景：回文链表判断、字符串排列验证
实现技巧：

# 回文链表判断示例
def isPalindrome(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    return values == values[::-1]
# 优化版：反转后半链表比较
def isPalindromeOptimized(head):
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    # 反转后半链表
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    # 比较前后两部分
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

关键点：通过快指针定位中点，反转后半链表实现O(1)空间复杂度。

三、双指针的进阶技巧

1. 指针初始化策略：根据问题特性选择起始位置，如链表问题常从head开始，数组问题可能从0或n-1开始。
2. 移动条件控制：严格区分while循环的终止条件（如left <= right vs left < right）。
3. 去重处理：在三数之和问题中，外层循环后需跳过重复元素：

   # 三数之和去重示例
   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:
                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
            elif s < 0:
                left += 1
            else:
                right -= 1
    return res

4. 边界条件处理：特别注意空指针、单元素链表、全相同元素数组等特殊情况。

四、双指针的实战训练建议

1. 基础题推荐：
   • LeetCode 27. 移除元素（左右指针）
   • LeetCode 167. 两数之和II（左右指针）
   • LeetCode 141. 环形链表（快慢指针）
2. 进阶题推荐：
   • LeetCode 76. 最小覆盖子串（滑动窗口）
   • LeetCode 15. 三数之和（左右指针+去重）
   • LeetCode 234. 回文链表（分裂指针）
3. 训练方法：
   • 每日3题：按类型分组练习（如周一练快慢指针，周二练滑动窗口）
   • 代码复盘：对比标准答案优化移动逻辑
   • 复杂度分析：验证每次指针移动是否有效减少问题规模

五、双指针的误区警示

1. 指针移动越界：在链表操作中未检查next节点是否存在
2. 循环条件错误：将left <= right误写为left < right导致漏解
3. 去重不彻底：仅处理外层循环重复而忽略内层循环重复
4. 空间复杂度误判：滑动窗口问题中错误使用额外数据结构

通过系统化的分类学习和针对性训练，双指针技术可成为解决LeetCode中等难度题目的利器。建议开发者从基础类型入手，逐步掌握指针移动的数学规律，最终实现算法复杂度的质变优化。