数组、链表与区间技巧

“数组、链表与区间技巧”这一块，我曾经有一种很典型的错觉：内容看懂了，自己也会了。我真正关掉答案后才发现：我曾经把数组题、链表题和区间题分开刷，后来才看出它们经常都在维护位置、边界和局部状态。后来我用画图、手算和最小代码反复验证，才把表面的熟悉变成可以复述的理解。

数组、链表与区间技巧是算法题里最常见的一组基本功。它们看起来都不难，但最考验边界、指针移动和状态维护。

这一章适合反复练。因为大量中等难度题，本质上不是高级算法，而是把数组、链表、哈希、窗口、区间这些技巧组合起来。

先从一排数字开始

假设有一排每天的销量。你可能要找某个值、统计一段时间总量、找连续增长区间，或批量修改某几天的数据。直接为每个问题重新扫描当然能做，但查询次数增加后会越来越慢。

• 双指针让两个边界各自只向前走。
• 滑动窗口复用相邻区间的统计结果。
• 二分查找每次排除一半候选。
• 前缀和提前保存累计结果。
• 扫描线把区间变化集中到端点处理。

第一次学习不需要一次掌握全部技巧。先保证下标不越界、循环能终止、状态更新顺序正确，再考虑优化。

我为什么先补这一章

这一章重点训练：

1. 如何用边界缩小搜索范围。
2. 如何用哈希记录历史状态。
3. 如何把区间查询、区间修改、重叠统计统一起来。
4. 如何避免链表断链、空指针、漏节点。

我自己的学习顺序

建议先从线性扫描开始，再进入更复杂的维护结构：

1. 数组与哈希题型。
2. 双指针与滑动窗口。
3. 二分查找。
4. 前缀和与差分数组。
5. 链表算法。
6. 单调栈与单调队列。
7. 区间与扫描线算法。
8. 矩阵与网格算法。
9. 位运算、Bitmap 与状态压缩。

我当时最容易混淆的地方

二分查找不是只找数组里的某个数，它更常见的本质是“找第一个满足条件的位置”。

滑动窗口不是固定模板，而是两个动作：

• 什么时候右边界扩张。
• 什么时候左边界收缩。

前缀和适合多次区间查询，差分适合多次区间修改。二者方向相反，但都在利用“前后状态的差”。

我后来这样检查自己是否真的理解

• 为什么双指针能把很多双重循环优化成线性？
• 为什么滑动窗口通常要求窗口状态可以被增删维护？
• 链表反转时，为什么一定要先保存 next？
• 扫描线为什么要把区间拆成开始事件和结束事件？