1. 怎么看数组题

数组题是算法刷题的入口,但真正考的通常不是“数组怎么用”,而是“下标怎么移动、区间怎么定义、状态怎么维护”。

数组的优势是可以用下标直接访问任意元素,nums[i] 是 O(1)O(1)。它的劣势是插入和删除常常要移动大量元素,所以很多数组题会要求我们用指针覆盖、用区间统计,或者用预处理避免重复扫描。

刷数组题时,我先按问题类型分类:

  • 如果数组有序,优先想二分查找。
  • 如果要求原地删除、移动、覆盖,优先想快慢指针。
  • 如果从两端选数、比较两端大小,优先想左右指针。
  • 如果题目反复出现“连续子数组 / 连续子串”,优先想滑动窗口或前缀和。
  • 如果题目反复修改区间,优先想差分。
  • 如果题目描述的是方向、边界、顺时针、逆时针,优先想模拟。

这篇笔记按方法讲,不按题号讲。每个方法里会直接放代码骨架、典型例题和容易错的地方,这样复习时能顺着一种思路看完。

2. 二分查找:在有序结构里缩小答案范围

二分查找适用于“答案具有单调性”的问题。最直观的是有序数组里找某个数,例如升序数组中 target 左边的值都偏小,右边的值都偏大,因此可以每次看中点并排除一半。

二分不只用于“找一个值”,更常用于“找边界”。比如找第一个大于等于 target 的位置、找最后一个小于等于 target 的位置、找插入位置,本质都是在一段单调条件中找到分界点。

2.1 先固定区间定义

二分最容易错的不是思想,而是边界。建议先固定一种写法,不要每道题临场切换。

左闭右闭 [left, right] 适合查找具体值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1

while left <= right:
mid = left + (right - left) // 2

if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1

这里 left 和 right 都是可能答案,所以循环条件是 left <= right。当 nums[mid] < target 时,mid 已经不可能是答案,所以下一次从 mid + 1 开始。

左闭右开 [left, right) 更适合找边界:

1
2
3
4
5
6
7
8
9
10
11
12
def lower_bound(nums: list[int], target: int) -> int:
left, right = 0, len(nums)

while left < right:
mid = left + (right - left) // 2

if nums[mid] < target:
left = mid + 1
else:
right = mid

return left

这个函数返回第一个 >= target 的位置。注意它返回的是“位置”,不保证这个位置的值一定等于 target。如果要判断目标值是否存在,还要检查:

1
2
pos = lower_bound(nums, target)
exists = pos < len(nums) and nums[pos] == target

下面用 nums = [1, 3, 5, 6, 8, 10]、target = 7 演示 lower_bound 如何找第一个 >= target 的位置。蓝色表示当前搜索区间 [left, right),橙色表示 mid,红色表示被排除的区间,绿色表示最终答案。

二分边界演示 target = 7 找第一个 >= target 的位置
left:0 right:6 mid:- 答案:-

2.2 典型例题怎么想

704. 二分查找:题目给一个升序数组和一个目标值,要求返回目标值下标,不存在返回 -1。这道题是二分的基本盘,重点不是难度,而是练习统一边界:如果用左闭右闭,就坚持 right = len(nums) - 1 和 while left <= right。

35. 搜索插入位置:题目要求在升序数组里找到 target,如果不存在,就返回它应该插入的位置。它看起来像查找,实际上是找第一个 >= target 的位置,所以更适合直接用 lower_bound。例如 nums = [1, 3, 5, 6],target = 2,第一个大于等于 2 的位置是下标 1。

34. 在排序数组中查找元素的第一个和最后一个位置:题目要求返回 target 出现区间的左右边界。做法是两次二分:第一次找第一个 >= target 的位置,第二次找第一个 >= target + 1 的位置,右边界就是第二个位置减一。更通用的写法是分别找 target 的左边界和 target 的右边界。

二分题最常见的易错点:

  • 区间定义混用。right = len(nums) 时不要写 while left <= right。
  • 找边界后忘记检查目标值是否真的存在。
  • mid 被排除时没有加一或减一,导致死循环。
  • 看到“有序”只想到查值,没有想到“找第一个满足条件的位置”。

3. 快慢指针:原地处理数组

快慢指针适合处理“扫描一遍数组,同时把有效元素放到前面”的问题。它最常见的语义是:

  • fast:负责遍历原数组,发现哪些元素要保留。
  • slow:负责标记下一个写入位置。

也就是说,[0, slow) 通常表示已经处理好的有效区域。只要 fast 指向的元素应该保留,就写到 nums[slow],然后 slow += 1。

3.1 原地删除不是物理删除

很多题会说“原地删除元素”,但在 LeetCode 里通常只要求返回新长度。数组后面的内容不用管,因为判题只看前 k 个元素。

比如删除所有等于 val 的元素:

1
2
3
4
5
6
7
8
9
def remove_value(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

这段代码的含义很清楚:fast 每次看一个元素,如果这个元素不等于 val,就把它放进有效区尾部。

3.2 典型例题怎么想

27. 移除元素:题目给一个数组和一个值 val,要求原地移除所有等于 val 的元素,并返回新长度。这道题就是快慢指针最标准的应用。不要用 nums.remove(),因为一边遍历一边删除容易跳过元素,而且每次删除都是 O(n)O(n)。

26. 删除有序数组中的重复项:题目给一个非递减数组,要求每个元素只保留一次。因为数组有序,相同元素一定相邻。可以让 slow 指向已保留区域的末尾,如果 nums[fast] != nums[slow - 1],说明遇到新元素,写到 nums[slow]。

1
2
3
4
5
6
7
8
9
10
11
def remove_duplicates(nums: list[int]) -> int:
if not nums:
return 0

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

return slow

283. 移动零:题目要求把所有 0 移到数组末尾,同时保持非零元素的相对顺序。可以先用快慢指针把非零元素写到前面,再把后面补零。

下面用 nums = [0, 1, 0, 3, 12] 演示这个过程。fast 负责扫描原数组,slow 永远指向“下一个非零元素应该写入的位置”。扫描结束后,slow 后面的区域统一补 0。

移动零演示 nums = [0, 1, 0, 3, 12] fast 扫描,slow 写入
fast:- slow:0 阶段:扫描非零
1
2
3
4
5
6
7
8
9
10
def move_zeroes(nums: list[int]) -> None:
slow = 0

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

for i in range(slow, len(nums)):
nums[i] = 0

快慢指针题最常见的易错点:

  • 把 slow 理解成当前遍历位置。实际上它通常是“下一个写入位置”。
  • 原地删除题返回了数组,而不是返回新长度。
  • 在遍历数组时调用 remove 或 pop,导致元素移动后漏扫。
  • 写入后忘记 slow += 1。

4. 左右指针:从两端向中间收缩

左右指针适合“答案和两端元素有关”的问题。最常见场景是有序数组:左端小、右端大,两个数的和偏小就移动左指针,偏大就移动右指针。

这类题的关键是理解为什么可以移动某个指针。不是因为“模板这么写”,而是因为当前选择已经不可能得到更优答案。

4.1 有序数组里的两数关系

在升序数组中,如果 nums[left] + nums[right] < target,说明当前和太小。此时固定 right,left 再往左也只会更小,所以只能让 left 右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]:
left, right = 0, len(nums) - 1

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

if total == target:
return left, right
if total < target:
left += 1
else:
right -= 1

return -1, -1

4.2 典型例题怎么想

977. 有序数组的平方:题目给一个非递减数组,数组里可能有负数,要求返回每个数平方后的非递减数组。平方后最大值一定来自原数组两端,因为负数绝对值可能很大,正数本身也可能很大。所以用 left 和 right 比较两端平方值,从结果数组尾部往前填。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sorted_squares(nums: list[int]) -> list[int]:
left, right = 0, len(nums) - 1
ans = [0] * len(nums)
pos = len(nums) - 1

while left <= right:
left_square = nums[left] * nums[left]
right_square = nums[right] * nums[right]

if left_square > right_square:
ans[pos] = left_square
left += 1
else:
ans[pos] = right_square
right -= 1
pos -= 1

return ans

这道题容易错在从前往后填。因为每次能确定的是“当前最大平方值”,所以应该从后往前放。

167. 两数之和 II - 输入有序数组:题目给一个升序数组,要求找两个数之和等于目标值。它是左右指针最典型的有序数组题。注意 LeetCode 这题返回的是从 1 开始的下标,不是 Python 的 0 基下标。

左右指针题最常见的易错点:

  • 没有利用有序性,只用暴力两层循环。
  • 该从结果末尾填的时候从开头填,例如有序数组平方。
  • 返回下标时忘记题目要求是 0 基还是 1 基。
  • while left < right 和 while left <= right 用错。两数问题通常不能用同一个元素两次,所以是 left < right;平方数组处理每个元素,所以是 left <= right。

5. 滑动窗口:维护一个连续区间

滑动窗口适合处理连续子数组或连续子串。它本质上也是双指针,但语义更明确:

  • left 和 right 共同维护窗口 [left, right]。
  • right 向右扩张,把新元素加入窗口。
  • 当窗口满足或不满足条件时,移动 left 收缩窗口。

滑动窗口成立的前提通常是窗口状态具有某种单调性。比如数组元素都是正数时,右扩会让窗口和变大,左缩会让窗口和变小,所以可以用窗口找最短满足条件的区间。

5.1 最短窗口:满足条件后尽量缩

209. 长度最小的子数组:题目给一个正整数数组和目标值 target,要求找和至少为 target 的最短连续子数组长度。因为所有数都是正数,所以窗口和会随着右指针右移而增加,随着左指针右移而减少。

下面用 target = 7、nums = [2, 3, 1, 2, 4, 3] 观察一次完整过程。蓝色区域是当前窗口,绿色边框表示当前找到的最短长度,橙色表示刚加入窗口的元素,红色表示刚被移出窗口的元素。

滑动窗口演示 target = 7 nums = [2, 3, 1, 2, 4, 3]
left:- right:- 窗口和:0 最短长度:∞
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def min_subarray_len(target: int, nums: list[int]) -> int:
left = 0
window_sum = 0
ans = float("inf")

for right, num in enumerate(nums):
window_sum += num

while window_sum >= target:
ans = min(ans, right - left + 1)
window_sum -= nums[left]
left += 1

return 0 if ans == float("inf") else ans

这道题的关键是:一旦窗口和已经满足条件,就要立刻尝试收缩左边界,因为题目要最短长度。

易错点是把 if window_sum >= target 写成一次判断。窗口可能连续缩很多次,每缩一次都可能得到更短答案,所以这里必须用 while。

5.2 最长窗口:不合法时再缩

904. 水果成篮:题目可以理解为:给一个数组,每个数字是一种水果,要求找最长连续区间,使区间里最多只有两种水果。这里窗口状态是“每种水果出现次数”。当窗口中水果种类超过 2 时,就移动左指针直到重新合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict


def total_fruit(fruits: list[int]) -> int:
count = defaultdict(int)
left = 0
ans = 0

for right, fruit in enumerate(fruits):
count[fruit] += 1

while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1

ans = max(ans, right - left + 1)

return ans

这类题的答案通常在窗口恢复合法后更新。因为题目要最长合法窗口,不合法时不能更新。

5.3 覆盖窗口:同时维护 need 和 window

76. 最小覆盖子串:题目给字符串 s 和 t,要求在 s 中找一个最短子串,使它包含 t 中所有字符及对应次数。这题比 209 难,因为窗口条件不是一个和,而是字符频率是否覆盖。

思路是:

  • need 记录目标字符需要多少个。
  • window 记录当前窗口已有多少个。
  • valid 记录有多少种字符已经满足需求。
  • 当 valid == len(need) 时,说明窗口已经覆盖,可以尝试收缩。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import Counter, defaultdict


def min_window(s: str, t: str) -> str:
need = Counter(t)
window = defaultdict(int)
valid = 0
left = 0
start = 0
length = float("inf")

for right, ch in enumerate(s):
if ch in need:
window[ch] += 1
if window[ch] == need[ch]:
valid += 1

while valid == len(need):
if right - left + 1 < length:
start = left
length = right - left + 1

remove_ch = s[left]
left += 1

if remove_ch in need:
if window[remove_ch] == need[remove_ch]:
valid -= 1
window[remove_ch] -= 1

return "" if length == float("inf") else s[start:start + length]

滑动窗口题最常见的易错点:

  • 没想清楚什么时候收缩。最短窗口通常是满足条件后收缩;最长窗口通常是不合法时收缩。
  • 用 if 代替 while,导致窗口没有收缩到极限。
  • 含负数数组里直接套正数窗口。比如“和至少为 K 的最短子数组”如果允许负数,窗口和不再单调,就不能直接用 209 的做法。
  • 右边界是 right,窗口长度是 right - left + 1,不要写成 right - left。

6. 前缀和:把区间统计变成两次查询

前缀和适合处理区间和、子数组和、频繁查询区间统计的问题。它的核心是先存从开头到当前位置之前的累积和。

定义:

1
prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]

这样区间 [left, right] 的和就是:

1
prefix[right + 1] - prefix[left]

多开一个 prefix[0] = 0 的好处是不用特殊处理从下标 0 开始的区间。

1
2
3
4
5
6
7
8
9
10
11
def build_prefix(nums: list[int]) -> list[int]:
prefix = [0] * (len(nums) + 1)

for i, num in enumerate(nums):
prefix[i + 1] = prefix[i] + num

return prefix


def range_sum(prefix: list[int], left: int, right: int) -> int:
return prefix[right + 1] - prefix[left]

6.1 典型例题怎么想

303. 区域和检索 - 数组不可变:题目会多次询问数组某个区间的元素和。每次都重新遍历会重复计算,所以初始化时构建前缀和,每次查询用两个前缀值相减。

560. 和为 K 的子数组:题目要求统计和为 k 的连续子数组数量,数组中可能有负数。这时不能用滑动窗口,因为窗口和不具备单调性。可以用前缀和 + 哈希表:如果当前前缀和是 cur,想找一个之前的前缀和 prev,满足 cur - prev = k,也就是 prev = cur - k。

下面用 nums = [1, 2, 1, 2]、k = 3 演示这个过程。每扫到一个位置,先计算当前前缀和 cur,再去哈希表里找 cur - k 出现过几次。出现几次,就说明有几个以当前位置结尾的子数组和为 k。

和为 K 的子数组演示 nums = [1, 2, 1, 2] k = 3
i:- cur:0 cur - k:- 答案:0
历史前缀和计数 count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import defaultdict


def subarray_sum(nums: list[int], k: int) -> int:
count = defaultdict(int)
count[0] = 1
cur = 0
ans = 0

for num in nums:
cur += num
ans += count[cur - k]
count[cur] += 1

return ans

这道题很适合区分滑动窗口和前缀和:如果数组都是正数,很多区间和问题可以滑动;如果有负数,优先想前缀和。

前缀和题最常见的易错点:

  • prefix 没有多开一位,导致 left == 0 要单独处理。
  • 区间 [left, right] 写成 prefix[right] - prefix[left],少算了右端点。
  • 统计子数组个数时,忘记先放 count[0] = 1,导致从下标 0 开始的子数组漏掉。
  • 先更新 count[cur] 再统计答案,可能把当前前缀和当成之前的前缀和。

7. 差分:批量处理区间加减

差分可以看作前缀和的逆操作。前缀和擅长查询区间统计,差分擅长处理多次区间修改。

如果要给区间 [left, right] 全部加 val,不需要把每个位置都加一遍,只需要记录边界变化:

1
2
diff[left] += val
diff[right + 1] -= val

最后对 diff 做一次前缀累加,就能得到每个位置的最终值。

下面用长度为 5 的数组演示两次区间修改:

1
2
[1, 3] + 2
[2, 4] + 3

先不要急着看最终数组,重点观察 diff:每次区间加法只改两个边界。等所有修改都记录完,再从左到右累加 diff,才得到真正的结果数组。

差分区间修改演示 n = 5 操作:[1,3]+2,[2,4]+3
差分数组 diff(多开一位,长度 n + 1)
还原后的数组 ans(长度 n)
阶段:初始化 当前 i:- cur:0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def apply_range_updates(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
diff = [0] * (n + 1)

for left, right, val in updates:
diff[left] += val
if right + 1 < len(diff):
diff[right + 1] -= val

ans = [0] * n
cur = 0

for i in range(n):
cur += diff[i]
ans[i] = cur

return ans

7.1 典型例题怎么想

1109. 航班预订统计:题目给若干条预订记录,每条记录表示从第 first 个航班到第 last 个航班都增加若干座位,要求返回每个航班最终被预订的座位数。每条记录都是一次区间加法,所以用差分。注意题目航班编号从 1 开始,数组下标从 0 开始,写代码时要统一换成 0 基。

1094. 拼车:题目给若干乘客行程,每条行程表示在某站上车、某站下车,车容量有限,问是否会超载。上车点是区间加的开始,下车点是区间加的结束之后;用差分统计每个位置车上人数,一旦超过容量就返回 False。

差分题最常见的易错点:

  • 题目编号从 1 开始,代码下标从 0 开始,忘记转换。
  • right + 1 越界。可以多开一位,或者判断后再减。
  • 区分闭区间和半开区间。拼车里乘客在 to 已经下车,所以影响区间通常是 [from, to)。
  • 最后忘记做前缀累加,只改了差分数组。

8. 矩阵模拟:先定边界,再按方向走

模拟题没有统一数学公式,但有统一的整理方式:把状态写清楚。数组模块里最典型的是螺旋矩阵。

螺旋矩阵可以用四个边界表示还没遍历的范围:

  • top:上边界
  • bottom:下边界
  • left:左边界
  • right:右边界

每一圈按右、下、左、上的顺序走。走完一条边,就收缩对应边界。

下面用一个 3 x 4 矩阵演示读取顺序。橙色是当前正在读取的位置,绿色是已经加入答案的元素,蓝色区域表示当前边界内还没有处理完的部分。

螺旋矩阵演示 matrix = 3 x 4 方向:右 → 下 → 左 → 上
当前矩阵
方向:准备开始 top:0 bottom:2 left:0 right:3
输出顺序 ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def spiral_order(matrix: list[list[int]]) -> list[int]:
if not matrix or not matrix[0]:
return []

top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
ans = []

while top <= bottom and left <= right:
for col in range(left, right + 1):
ans.append(matrix[top][col])
top += 1

for row in range(top, bottom + 1):
ans.append(matrix[row][right])
right -= 1

if top <= bottom:
for col in range(right, left - 1, -1):
ans.append(matrix[bottom][col])
bottom -= 1

if left <= right:
for row in range(bottom, top - 1, -1):
ans.append(matrix[row][left])
left += 1

return ans

8.1 典型例题怎么想

54. 螺旋矩阵:题目给一个矩阵,要求按顺时针螺旋顺序输出所有元素。这题最容易在单行、单列、最后一圈时重复遍历,所以每走反向边前都要检查边界是否仍然合法。

59. 螺旋矩阵 II:题目给整数 n,要求生成一个 n x n 的矩阵,按螺旋顺序填入 1 到 n^2。它和 54 的方向相同,只是从“读取矩阵”变成“写入矩阵”。仍然用四个边界,走一步填一个数。

模拟题最常见的易错点:

  • 没有在每条边走完后及时收缩边界。
  • 单行或单列时重复访问同一条边。
  • range 的结束位置写错,尤其是反向遍历时。
  • 一边写代码一边猜方向,导致状态混乱。最好先画一圈,再写循环。

9. 复习总览

  • 有序数组里找值或找边界:二分查找。先固定区间定义,再写循环。
  • 原地删除、去重、移动元素:快慢指针。slow 是下一个写入位置。
  • 有序数组两端比较、平方排序、两数之和:左右指针。谁不可能产生答案,就移动谁。
  • 连续区间且窗口状态可维护:滑动窗口。最短窗口满足后收缩,最长窗口不合法时收缩。
  • 区间和、多次查询、含负数的子数组和统计:前缀和。
  • 多次区间加减:差分。只改区间起点和终点后一位。
  • 矩阵方向题:模拟。先定 top/bottom/left/right,再按方向走。

数组题复习时最重要的是说清楚每个指针或数组的含义:left 表示什么,right 表示什么,slow 表示什么,prefix[i] 表示什么。含义清楚,代码就不容易散。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。
最新文章
网站信息
文章数目 :
18
最后更新时间 :