双指针 · Two Pointers

一句话骨架：在有序或对撞的场景下，左右指针向中间收缩；移动的关键不是"轮流走"，而是根据当前情况选择该移动的一侧——这一选择决定了能否把 O(n²) 压到 O(n)。

何时用

• 数组有序 → 对撞双指针（盛水容器、三数之和）
• 字符串/数组中维护一段"区间"且能单调收缩 → 同向双指针（移动零、回文判断）
• 两个串/链表对齐扫描（合并两个有序链表、相交链表）

通用模板

left, right = 0, len(arr) - 1
while left < right:
    # 1. 计算当前状态
    cur = f(arr[left], arr[right])
    # 2. 更新最优
    best = max(best, cur)
    # 3. 决定移动哪一侧（核心难点）
    if 应该缩左:
        left += 1
    else:
        right -= 1

关卡 1 · 盛最多水的容器

#11盛最多水的容器中等

♥♥♥♥♥+0 XP🔥 0

0 / 10

📝 题目

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1

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

输出49

💡 取 i=1(高8) 与 i=8(高7)，宽度 7，min(8,7)*7 = 49

示例 2

输入height = [1,1]

输出1

约束

• n == height.length
• 2 ≤ n ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴

💡 思路：对撞双指针。面积 = min(左高, 右高) × 宽度。每次移动较矮的那一侧——因为如果移动较高的，下一次 min 不会变大，宽度还在变小，面积只会更糟。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def maxArea(height: list[int]) -> int: 2    left, right = 0, len(height) - 1 3    best = 0 4    while left < right: 5        h = min(height[left], height[right]) 6        best = max(best, h * (right - left)) 7        if height[left] < height[right]: 8            left += 1 9        else:10            right -= 111    return best

🐞 单步可视化

示例：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

代码L2

 1def maxArea(height: list[int]) -> int: 2    left, right = 0, len(height) - 1 3    best = 0 4    while left < right: 5        h = min(height[left], height[right]) 6        best = max(best, h * (right - left)) 7        if height[left] < height[right]: 8            left += 1 9        else:10            right -= 111    return best

数据流

L0R8best0

height

0

1

L

1

8

2

6

3

2

4

5

5

4

6

8

7

3

8

7

R

result0

1 / 51初始化对撞双指针：left=0, right=8

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

双指针应该如何初始化？

 1def maxArea(height: list[int]) -> int: 2    left, right = 0, len(height) - 1 3    best = 0 4    while left < right: 5        h = min(height[left], height[right]) 6        best = max(best, h * (right - left)) 7        if height[left] < height[right]: 8            left += 1 9        else:10            right -= 111    return best

循环条件应该是？

 1def maxArea(height: list[int]) -> int: 2    left, right = 0, len(height) - 1 3    best = 0 4    while left < right: 5        h = min(height[left], height[right]) 6        best = max(best, h * (right - left)) 7        if height[left] < height[right]: 8            left += 1 9        else:10            right -= 111    return best

当前容器的高度由谁决定？

宽度应该怎么算？

指针移动的核心策略：每次应该移动哪一侧？

当 height[left] == height[right] 时移动谁？

为什么这个贪心策略不会错过最优解？

时间复杂度是？

空间复杂度是？

把暴力 O(n²) 优化成 O(n) 的关键认知是？

关卡 2 · 三数之和

排序 + 固定 i + 内层对撞双指针。三处去重是细节决定成败的地方——很多人栽在"找到解后只移一格"上。

#15三数之和中等

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1

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

输出[[-1,-1,2],[-1,0,1]]

示例 2

输入nums = [0,1,1]

输出[]

示例 3

输入nums = [0,0,0]

输出[[0,0,0]]

💡 同值但来自不同位置算合法

约束

• 3 ≤ nums.length ≤ 3000
• -10⁵ ≤ nums[i] ≤ 10⁵

💡 思路：排序 + 固定一个数 + 双指针。固定 nums[i]，在 i+1..n-1 上用对撞双指针找两数之和 = -nums[i]。去重三处：i 跳过相同、找到解后 left/right 各自跳过相同。

✅ 完整解法

时间 O(n²) · 空间 O(1) 不计排序

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

🐞 单步可视化

示例：nums = [-1, 0, 1, 2, -1, -4]

代码L2

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

数据流

res.size0

nums（已排序）

0

-4

1

-1

2

-1

3

0

4

1

5

2

result

1 / 29排序后：nums = [-4, -1, -1, 0, 1, 2]

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么第一步要 nums.sort()？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

Python 里 nums.sort() 与 sorted(nums) 的区别？

for i in range(n - 2) 为什么是 n - 2 而不是 n？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

if nums[i] > 0: break 这个剪枝的依据是？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

外层去重 if i > 0 and nums[i] == nums[i-1]: continue 的关键点？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

内层双指针的初始化应该是？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

当 s = 0（找到一组解）后，立刻只做 left += 1; right -= 1 是否够？

s < 0 时应该移动谁？

 1def threeSum(nums: list[int]) -> list[list[int]]: 2    nums.sort() 3    n = len(nums) 4    res = [] 5    for i in range(n - 2): 6        if nums[i] > 0: 7            break 8        if i > 0 and nums[i] == nums[i - 1]: 9            continue10        left, right = i + 1, n - 111        while left < right:12            s = nums[i] + nums[left] + nums[right]13            if s == 0:14                res.append([nums[i], nums[left], nums[right]])15                while left < right and nums[left] == nums[left + 1]:16                    left += 117                while left < right and nums[right] == nums[right - 1]:18                    right -= 119                left += 120                right -= 121            elif s < 0:22                left += 123            else:24                right -= 125    return res

时间复杂度是？

空间复杂度是？

能否改为"用 set 去重最后输出"代替三处去重？

同 pattern 索引

题号	题名	难度	关键变形
42	接雨水	困难	双指针维护 left_max / right_max，移较矮一侧
283	移动零	简单	同向双指针，slow 指向"下一个非零落脚点"
88	合并两个有序数组	简单	倒序双指针避免覆盖

面试常踩

1. 越界检查放在 while 条件里——例如三数之和内层去重 while left < right and nums[left] == nums[left+1]，少了 left < right 会越界。
2. 找到解后必须跳过相同元素——只移一格会重复。
3. 对撞双指针的"贪心移动"要会讲清楚：移动较高侧时，新的 min 不会增、宽度还在减，面积只会更糟。这是面试时区分"会写"和"懂为什么"的分水岭。