1. 怎么看数组题
数组题是算法刷题的入口,但真正考的通常不是“数组怎么用”,而是“下标怎么移动、区间怎么定义、状态怎么维护”。
数组的优势是可以用下标直接访问任意元素,nums[i] 是 。它的劣势是插入和删除常常要移动大量元素,所以很多数组题会要求我们用指针覆盖、用区间统计,或者用预处理避免重复扫描。
刷数组题时,我先按问题类型分类:
- 如果数组有序,优先想二分查找。
- 如果要求原地删除、移动、覆盖,优先想快慢指针。
- 如果从两端选数、比较两端大小,优先想左右指针。
- 如果题目反复出现“连续子数组 / 连续子串”,优先想滑动窗口或前缀和。
- 如果题目反复修改区间,优先想差分。
- 如果题目描述的是方向、边界、顺时针、逆时针,优先想模拟。
这篇笔记按方法讲,不按题号讲。每个方法里会直接放代码骨架、典型例题和容易错的地方,这样复习时能顺着一种思路看完。
2. 二分查找:在有序结构里缩小答案范围
二分查找适用于“答案具有单调性”的问题。最直观的是有序数组里找某个数,例如升序数组中 target 左边的值都偏小,右边的值都偏大,因此可以每次看中点并排除一半。
二分不只用于“找一个值”,更常用于“找边界”。比如找第一个大于等于 target 的位置、找最后一个小于等于 target 的位置、找插入位置,本质都是在一段单调条件中找到分界点。
2.1 先固定区间定义
二分最容易错的不是思想,而是边界。建议先固定一种写法,不要每道题临场切换。
左闭右闭 [left, right] 适合查找具体值:
1 | def binary_search(nums: list[int], target: int) -> int: |
这里 left 和 right 都是可能答案,所以循环条件是 left <= right。当 nums[mid] < target 时,mid 已经不可能是答案,所以下一次从 mid + 1 开始。
左闭右开 [left, right) 更适合找边界:
1 | def lower_bound(nums: list[int], target: int) -> int: |
这个函数返回第一个 >= target 的位置。注意它返回的是“位置”,不保证这个位置的值一定等于 target。如果要判断目标值是否存在,还要检查:
1 | pos = lower_bound(nums, target) |
下面用 nums = [1, 3, 5, 6, 8, 10]、target = 7 演示 lower_bound 如何找第一个 >= target 的位置。蓝色表示当前搜索区间 [left, right),橙色表示 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 | def remove_value(nums: list[int], val: int) -> int: |
这段代码的含义很清楚:fast 每次看一个元素,如果这个元素不等于 val,就把它放进有效区尾部。
3.2 典型例题怎么想
27. 移除元素:题目给一个数组和一个值 val,要求原地移除所有等于 val 的元素,并返回新长度。这道题就是快慢指针最标准的应用。不要用 nums.remove(),因为一边遍历一边删除容易跳过元素,而且每次删除都是 。
26. 删除有序数组中的重复项:题目给一个非递减数组,要求每个元素只保留一次。因为数组有序,相同元素一定相邻。可以让 slow 指向已保留区域的末尾,如果 nums[fast] != nums[slow - 1],说明遇到新元素,写到 nums[slow]。
1 | def remove_duplicates(nums: list[int]) -> int: |
283. 移动零:题目要求把所有 0 移到数组末尾,同时保持非零元素的相对顺序。可以先用快慢指针把非零元素写到前面,再把后面补零。
下面用 nums = [0, 1, 0, 3, 12] 演示这个过程。fast 负责扫描原数组,slow 永远指向“下一个非零元素应该写入的位置”。扫描结束后,slow 后面的区域统一补 0。
1 | def move_zeroes(nums: list[int]) -> None: |
快慢指针题最常见的易错点:
- 把
slow理解成当前遍历位置。实际上它通常是“下一个写入位置”。 - 原地删除题返回了数组,而不是返回新长度。
- 在遍历数组时调用
remove或pop,导致元素移动后漏扫。 - 写入后忘记
slow += 1。
4. 左右指针:从两端向中间收缩
左右指针适合“答案和两端元素有关”的问题。最常见场景是有序数组:左端小、右端大,两个数的和偏小就移动左指针,偏大就移动右指针。
这类题的关键是理解为什么可以移动某个指针。不是因为“模板这么写”,而是因为当前选择已经不可能得到更优答案。
4.1 有序数组里的两数关系
在升序数组中,如果 nums[left] + nums[right] < target,说明当前和太小。此时固定 right,left 再往左也只会更小,所以只能让 left 右移。
1 | def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int]: |
4.2 典型例题怎么想
977. 有序数组的平方:题目给一个非递减数组,数组里可能有负数,要求返回每个数平方后的非递减数组。平方后最大值一定来自原数组两端,因为负数绝对值可能很大,正数本身也可能很大。所以用 left 和 right 比较两端平方值,从结果数组尾部往前填。
1 | def sorted_squares(nums: list[int]) -> list[int]: |
这道题容易错在从前往后填。因为每次能确定的是“当前最大平方值”,所以应该从后往前放。
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] 观察一次完整过程。蓝色区域是当前窗口,绿色边框表示当前找到的最短长度,橙色表示刚加入窗口的元素,红色表示刚被移出窗口的元素。
1 | def min_subarray_len(target: int, nums: list[int]) -> int: |
这道题的关键是:一旦窗口和已经满足条件,就要立刻尝试收缩左边界,因为题目要最短长度。
易错点是把 if window_sum >= target 写成一次判断。窗口可能连续缩很多次,每缩一次都可能得到更短答案,所以这里必须用 while。
5.2 最长窗口:不合法时再缩
904. 水果成篮:题目可以理解为:给一个数组,每个数字是一种水果,要求找最长连续区间,使区间里最多只有两种水果。这里窗口状态是“每种水果出现次数”。当窗口中水果种类超过 2 时,就移动左指针直到重新合法。
1 | from collections import defaultdict |
这类题的答案通常在窗口恢复合法后更新。因为题目要最长合法窗口,不合法时不能更新。
5.3 覆盖窗口:同时维护 need 和 window
76. 最小覆盖子串:题目给字符串 s 和 t,要求在 s 中找一个最短子串,使它包含 t 中所有字符及对应次数。这题比 209 难,因为窗口条件不是一个和,而是字符频率是否覆盖。
思路是:
need记录目标字符需要多少个。window记录当前窗口已有多少个。valid记录有多少种字符已经满足需求。- 当
valid == len(need)时,说明窗口已经覆盖,可以尝试收缩。
1 | from collections import Counter, defaultdict |
滑动窗口题最常见的易错点:
- 没想清楚什么时候收缩。最短窗口通常是满足条件后收缩;最长窗口通常是不合法时收缩。
- 用
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 | def build_prefix(nums: list[int]) -> list[int]: |
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。
1 | from collections import defaultdict |
这道题很适合区分滑动窗口和前缀和:如果数组都是正数,很多区间和问题可以滑动;如果有负数,优先想前缀和。
前缀和题最常见的易错点:
prefix没有多开一位,导致left == 0要单独处理。- 区间
[left, right]写成prefix[right] - prefix[left],少算了右端点。 - 统计子数组个数时,忘记先放
count[0] = 1,导致从下标 0 开始的子数组漏掉。 - 先更新
count[cur]再统计答案,可能把当前前缀和当成之前的前缀和。
7. 差分:批量处理区间加减
差分可以看作前缀和的逆操作。前缀和擅长查询区间统计,差分擅长处理多次区间修改。
如果要给区间 [left, right] 全部加 val,不需要把每个位置都加一遍,只需要记录边界变化:
1 | diff[left] += val |
最后对 diff 做一次前缀累加,就能得到每个位置的最终值。
下面用长度为 5 的数组演示两次区间修改:
1 | [1, 3] + 2 |
先不要急着看最终数组,重点观察 diff:每次区间加法只改两个边界。等所有修改都记录完,再从左到右累加 diff,才得到真正的结果数组。
1 | def apply_range_updates(n: int, updates: list[tuple[int, int, int]]) -> list[int]: |
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 矩阵演示读取顺序。橙色是当前正在读取的位置,绿色是已经加入答案的元素,蓝色区域表示当前边界内还没有处理完的部分。
1 | def spiral_order(matrix: list[list[int]]) -> list[int]: |
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] 表示什么。含义清楚,代码就不容易散。





