30 秒速览

  • 什么时候用：有序数组、原地操作、链表、需要 O(1) 空间
  • 核心思想：用两个指针的位置/速度差来解决问题
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

一、直觉建立

跑道上的两个人

想象两个人在跑道上跑步：

相向双指针：两人从跑道两端相向跑来，在某处相遇

  • 场景：有序数组两数之和、反转数组、回文判断、接雨水

同向双指针：两人从起点出发，一快一慢

  • 场景：快慢指针找中点、原地去重、移除元素、滑动窗口

关键思想：用两个指针的相对位置/速度差来解决问题，避免暴力枚举。

为什么双指针有效？

数学原理：双指针能够有效是因为它利用了问题的单调性或有序性。

以两数之和为例：

有序数组: [1, 2, 4, 7, 11]
目标: 9

暴力: 枚举所有 (i, j) 对，O(n²)
双指针: 利用有序性，O(n)

left=0, right=4: 1+11=12 > 9 → right--
left=0, right=3: 1+7=8 < 9 → left++
left=1, right=3: 2+7=9 == 9 → 找到！

为什么不会漏解？

  • 当 nums[left] + nums[right] > target 时，right 往左移
  • 这意味着：对于当前的 right，所有 left' > left 的组合都会更大，不可能是解
  • 所以可以安全地排除 right，不会漏解

二、三种模式详解

模式 1：相向双指针

两端向中间收缩，适用于有序数组。

def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    """有序数组两数之和"""
    i, j = 0, len(nums) - 1

    while i < j:
        s = nums[i] + nums[j]
        if s == target:
            return i, j
        if s < target:
            i += 1
        else:
            j -= 1

    return None

模式 2：同向双指针（快慢指针）

快指针遍历，慢指针标记"有效区域边界"。

def remove_element(nums: list[int], val: int) -> int:
    """原地移除元素"""
    slow = 0  # 慢指针：指向下一个要填入的位置

    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1

    return slow

模式 3：快慢指针（链表）

一个走一步，一个走两步，用于检测环、找中点。

def has_cycle(head) -> bool:
    """检测链表是否有环"""
    slow = fast = head

    while fast and fast.next:
        slow = slow.next      # 慢指针走一步
        fast = fast.next.next  # 快指针走两步

        if slow == fast:
            return True

    return False

三、典型例题

例题 1：LC 27. 移除元素

题目：给你一个数组 nums 和一个值 val，你需要原地移除所有等于 val 的元素，并返回移除后数组的新长度。

示例：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]

思路：快慢指针

初始: [3, 2, 2, 3], val = 3
       s
       f

f=0: nums[0]=3==val, 跳过
f=1: nums[1]=2!=val, nums[s]=nums[f], s++
      [2, 2, 2, 3]
          s
             f

f=2: nums[2]=2!=val, nums[s]=nums[f], s++
      [2, 2, 2, 3]
             s
                f

f=3: nums[3]=3==val, 跳过

最终: [2, 2, _, _], 返回 s=2

代码

def removeElement(nums: list[int], val: int) -> int:
    slow = 0  # 慢指针：指向下一个要填入的位置

    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1

    return slow

复杂度：时间 O(n)，空间 O(1)

例题 2：LC 977. 有序数组的平方

题目：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]

思路：相向双指针

原数组: [-4, -1, 0, 3, 10]
平方后: [16,  1, 0, 9, 100]

观察：最大值一定在两端！
- 负数越小，平方越大
- 正数越大，平方越大

用相向双指针，每次比较两端的平方，大的放入结果数组末尾

代码

def sortedSquares(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    pos = n - 1  # 从后往前填充

    while left <= right:
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2

        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
        pos -= 1

    return result

复杂度：时间 O(n)，空间 O(n)

例题 3：LC 15. 三数之和（重点）

题目：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。返回所有和为 0 且不重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路演进

暴力解法 O(n³)：三重循环枚举所有三元组

优化思路：

  1. 先排序 → 方便去重 + 使用双指针
  2. 固定第一个数 i，用双指针找剩余两数
  3. 去重：跳过相邻相同的元素

代码

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 2):
        # 去重：跳过相同的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 剪枝：如果最小值已经 > 0，不可能凑成 0
        if nums[i] > 0:
            break

        # 双指针找两数之和
        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            curr_sum = nums[left] + nums[right]

            if curr_sum == target:
                result.append([nums[i], nums[left], nums[right]])

                # 去重：跳过相同的 left 和 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 curr_sum < target:
                left += 1
            else:
                right -= 1

    return result

去重逻辑详解

nums = [-1, -1, 0, 1]
排序后: [-1, -1, 0, 1]

不去重会得到: [[-1, 0, 1], [-1, 0, 1]]
去重后: [[-1, 0, 1]]

去重的位置：

  • 对 i 去重：i > 0 and nums[i] == nums[i-1]（必须是 i-1，不能是 i+1）
  • 对 left/right 去重：在找到答案后跳过相同元素

复杂度：时间 O(n²)，空间 O(log n)（排序）

例题 4：LC 11. 盛最多水的容器

题目：给定 n 个非负整数 a1, a2, …, an，每个数代表一个垂直线段的高度。找出两条线，使得它们与 x 轴构成的容器可以容纳最多的水。

示例：

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49

思路：相向双指针

  |        |
  |        |  |
  |  |     |  |
  |  |  |  |  |
  |  |  |  |  |  |
  |  |  |  |  |  |  |
  |  |  |  |  |  |  |
  1  8  6  2  5  4  8  3  7

面积 = min(height[left], height[right]) × (right - left)

关键：移动较矮的那个指针！
- 移动较高的，面积一定减小（宽度减小，高度不可能增加）
- 移动较矮的，面积可能增大（高度可能增加）

代码

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        # 计算当前面积
        width = right - left
        h = min(height[left], height[right])
        max_area = max(max_area, width * h)

        # 移动较矮的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

复杂度：时间 O(n)，空间 O(1)

例题 5：LC 42. 接雨水（Hard）

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

图解:
   █
   █ █   █
 █ █ █ █ █ █ █
     ▓ ▓ ▓ ▓

思路：相向双指针

核心思想：每个位置能接的雨水 = min(左边最高, 右边最高) - 当前高度

关键观察：

  • 如果 left_max < right_max，则位置 left 的雨水量只取决于 left_max
  • 因为 min(left_max, right_max) = left_max

代码

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            # 左边矮，处理左边
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            # 右边矮，处理右边
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

复杂度：时间 O(n)，空间 O(1)

例题 6：LC 141. 环形链表

题目：给你一个链表的头节点 head，判断链表中是否有环。

思路：快慢指针

如果有环，快指针最终会追上慢指针。

代码

def hasCycle(head) -> bool:
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

复杂度：时间 O(n)，空间 O(1)

例题 7：LC 19. 删除链表的倒数第 N 个结点

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：快慢指针

  1. 快指针先走 n 步
  2. 快慢指针同时走，快指针到末尾时，慢指针正好在倒数第 n 个

代码

def removeNthFromEnd(head, n: int):
    dummy = ListNode(0, head)
    fast = slow = dummy

    # 快指针先走 n 步
    for _ in range(n):
        fast = fast.next

    # 快慢指针同时走
    while fast.next:
        fast = fast.next
        slow = slow.next

    # 删除倒数第 n 个
    slow.next = slow.next.next

    return dummy.next

复杂度：时间 O(n)，空间 O(1)

四、常见错误与陷阱

错误 1：三数之和忘记排序

# 错误：直接用双指针
left, right = i + 1, n - 1

# 正确：必须先排序
nums.sort()
left, right = i + 1, n - 1

错误 2：去重逻辑放错位置

# 错误：用 i+1 判断
if nums[i] == nums[i + 1]:  # ✗ 会漏掉有效答案
    continue

# 正确：用 i-1 判断
if i > 0 and nums[i] == nums[i - 1]:  # ✓
    continue

错误 3：快慢指针职责搞混

# 快慢指针：慢指针标记"有效区域边界"，快指针负责遍历
# 不要搞反了

错误 4：不理解为什么可以移动指针

只有问题具有单调性时，移动指针才不会漏解。

五、复盘清单

触发信号

  • 有序数组（相向双指针）
  • 需要原地操作（快慢指针）
  • 链表问题（快慢指针）
  • 需要找两个元素满足某条件（双指针）
  • 需要 O(1) 空间复杂度

边界条件

  • 空数组/空链表
  • 单元素
  • 所有元素相同
  • 两指针相遇时的处理

常见错误

  • 忘记排序
  • 去重逻辑位置错误
  • 循环条件错误（left < right vs left <= right）
  • 快慢指针初始位置错误

六、题目清单

基础题

题号题目难度考点
27移除元素Easy快慢指针
26删除有序数组中的重复项Easy快慢指针
283移动零Easy快慢指针
977有序数组的平方Easy相向双指针
141环形链表Easy快慢指针
876链表的中间结点Easy快慢指针

进阶题

题号题目难度考点
15三数之和Medium排序+双指针+去重
18四数之和Medium排序+双指针
11盛最多水的容器Medium相向双指针
42接雨水Hard双指针
19删除链表的倒数第 N 个结点Medium快慢指针
160相交链表Easy双指针