CHAPTER 02 · 线性技巧

数组与双指针

用快慢、左右指针压缩枚举范围,把很多平方级搜索降到线性级。

3 个知识小节7 道分层练习4–5 天 建议周期
展开本章目录
  1. 学习之前
  2. 1. 快慢指针与原地修改
  3. 2. 左右指针与单调收缩
  4. 3. 排序后的 nSum 去重
  5. 延伸阅读
  6. 分层练习
  7. 我的笔记
00

BEFORE LEARNING

先理解为什么学

双指针的本质是维护一段已经满足定义的区间,并利用顺序或单调性跳过不可能的组合。它是数组、链表和滑动窗口的共同基础。

开始前应具备

  • 完成复杂度与哈希章节
  • 理解数组下标和原地修改
  • 能描述闭区间与半开区间

完成本章后

  • 区分快慢指针与左右指针
  • 掌握原地修改数组
  • 能从单调性判断指针移动方向
01

CORE LESSONS

知识讲义

01

LESSON

快慢指针与原地修改

什么时候想到它?

要求在原数组上删除、去重或移动元素,并限制额外空间时使用。

快指针扫描所有输入,慢指针指向下一个有效写入位置。慢指针之前始终是已经整理好的答案区,因此无需真的删除数组元素。

推导步骤

  1. 定义慢指针之前的区间含义
  2. 快指针逐个检查元素
  3. 遇到保留元素时写入慢指针位置
  4. 返回有效区间长度或整理后的数组
思维模板 / 伪代码
slow = 0
for fast in range(n):
  if should_keep(a[fast]):
    a[slow] = a[fast]
    slow += 1
02

LESSON

左右指针与单调收缩

什么时候想到它?

数组有序,或区间两端的选择能确定哪一侧不可能成为更优答案时使用。

左右指针不是盲目夹逼。每次移动都必须排除一整组不可能解。以盛水问题为例,容量受短板限制,因此移动长板不会改善当前短板造成的上限。

推导步骤

  1. 确认输入的顺序或目标函数的单调性
  2. 计算当前左右端形成的候选答案
  3. 证明移动哪侧才能排除无效候选
  4. 直到区间为空或指针相遇
思维模板 / 伪代码
left, right = 0, n - 1
while left < right:
  update_answer(left, right)
  if move_left_condition: left += 1
  else: right -= 1
03

LESSON

排序后的 nSum 去重

什么时候想到它?

要求寻找多个元素的目标和,同时答案不能重复时,考虑排序后固定一个元素再双指针。

排序让和值随指针移动呈单调变化,也让重复值相邻。三数之和由此降为“枚举第一个数 + 两数之和”,并能在同一层跳过重复答案。

推导步骤

  1. 先排序
  2. 枚举当前层固定元素
  3. 在剩余区间使用左右指针
  4. 找到答案后同时跳过左右重复值
思维模板 / 伪代码
sort(a)
for i in range(n):
  if duplicate_i: continue
  left, right = i + 1, n - 1
  while left < right: compare_sum()
02

READING

延伸阅读

先读完本站讲义并尝试练习;遇到推导不清的地方,再回到原始教程深入阅读。

03

PRACTICE LADDER

按作用分层练习

题量由知识点决定,不再固定为 5 道。先完成“入门”和“模板”,再做变式与综合;挑战题可以留到复习阶段。

入门认识结构模板独立复现变式迁移条件综合组合技巧挑战延后突破
01

快慢指针与原地修改

3 道 · 依次完成

LC 27入门简单

移除元素

Remove Element

为什么选:最直接的原地写入练习。

快慢指针建议 15 分钟
打开 LeetCode ↗
LC 26模板简单

删除有序数组中的重复项

Remove Duplicates

为什么选:训练慢指针所代表的有效区间。

快慢指针建议 20 分钟
打开 LeetCode ↗
LC 283变式简单

移动零

Move Zeroes

为什么选:把删除转化为稳定移动并补零。

原地修改建议 20 分钟
打开 LeetCode ↗
02

左右指针与单调收缩

3 道 · 依次完成

LC 167模板中等

两数之和 II

Two Sum II

为什么选:有序数组中根据和值决定移动方向。

左右指针建议 20 分钟
打开 LeetCode ↗
LC 11综合中等

盛最多水的容器

Container With Most Water

为什么选:需要证明为什么移动短板。

左右指针建议 30 分钟
打开 LeetCode ↗
LC 42挑战困难

接雨水

Trapping Rain Water

为什么选:通过左右最大值建立更复杂的不变量。

双指针边界建议 60 分钟
打开 LeetCode ↗
03

排序后的 nSum 去重

1 道 · 依次完成

LC 15综合中等

三数之和

3Sum

为什么选:集中训练排序、固定元素、双指针和去重。

排序 + 双指针建议 45 分钟
打开 LeetCode ↗
04

PERSONAL NOTEBOOK

我的学习笔记

我如何识别这个模式?今天卡在哪里?下次需要先检查什么?

笔记保存在当前浏览器