0.前言

经常有人把学习CS比作“仓鼠轮”，暗指这是一个单调重复的记忆过程。我自认还是付出了一些努力，但大多数都只是机械的记忆。
随着学习的深入，我逐渐发现自己真正的短板在于“思考的深度”。最典型的例子就是算法。

1.时间复杂度考察

在实际业务（和刷题）中，评估一个算法必须同时权衡**平均（典型）和最劣（极端）**两种复杂度。

第一步：基于“数据量级”，估算“性能天花板”

首先，我们要根据输入的数据量 $N$ 来估算一个“可接受”的时间复杂度上限。这是对“典型情况”的粗略评估。

以算法题中常见的 $10^8$ 次操作为性能瓶颈为例：

  • 若 $N = 10^4$，$N^2 = 10^8$。这意味着 $O(n^2)$ 的算法已经逼近性能红线，非常危险，很可能超时。
  • 若 $N = 10^5$，$N \log N \approx 1.7 \times 10^6$。此时 $O(n \log n)$ 绰绰有余。
  • 若 $N = 10^8$，你甚至都不能用 $O(n)$，可能需要 $O(\log n)$ 或 $O(1)$。

第二步：基于“数据构造”，考察“最劣退化”

这是最关键也最容易被忽视的一步。我们必须去思考：

“是否存在某种极端的数据组合，能让我的算法性能急剧下降（退化）？”

最经典的例子就是快速排序 (QuickSort)：

  • 平均复杂度： $O(n \log n)$。它在绝大多数随机数据下表现优异。
  • 最劣复杂度： $O(n^2)$。当面对一个已经有序的数组（或所有元素都相同的数组）时，QuickSort 会退化成一个“最差”的排序。

如果我们只考虑了平均情况，盲目地认为自己写出了一个 $O(n \log n)$ 的算法，那么这种“最劣”情况就会导致程序在面对特定数据时莫名超时，这在排查问题时会让人非常抓狂。

2.分析不稳定因素

从枚举到查询

在处理子数组问题时，通常采用枚举右，维护左的做法，这是因为右可以将之前遍历过的自身作为左的已知信息，提供logn的查询路径（当然你反过来也可以，但比较反直觉）。

3.模拟思路

延迟登记

当查询 (l, r) 对有**“距离约束”**时（例如，子数组长度 $\ge 3$，即 l <= r - 2），
可以考虑在遍历 r 时只登记 r-2。

数据库架构

子数组计数问题：

WHERE (识别条件): 列出 l 必须满足的所有“时序条件”和“内容条件”。

“内容”条件（Key 1 和 Key 2）： 这些是关于 l 本身属性的条件（capacity[l] 是多少？sum[l+1] 是多少？）。 “内容”条件决定了 map 的“键”(Key)。

“时序”条件（Timing）： 这个条件（l <= r - 2）与 l 本身的值无关，只与它和 r 的**“相对位置”**有关。 “时序”条件决定了 map 的“更新策略”（即“延迟登记”）。

INDEX (设计 map):

用**“内容条件”（如 cap[l] == …, sum[l] == …）来设计 map 的嵌套 key**。

map 的**“值”**通常是你想要的（COUNT、MAX、MIN等）。

TIMING (设计更新):

用**“时序条件”（如 l < r, l <= r-k）来决定你“登记” l 的时机**（是登记 r？还是 r-k？）。