寻找所需线性模式时要提出的问题
Source: Dev.to
模式选择速查表
下面是一张 模式选择速查表。
阅读题目时，对每个模式自行提问下面列出的问题。
如果你的答案是 YES，则该模式很可能是正确的思路。
1. Sliding Window（固定大小）
提问这些问题：
- 题目是否在询问长度恰为
k的 subarrays/substrings？ - 我是否需要为 每个大小为 k 的窗口 计算某些值（sum、max、count）？
- 暴力解的时间复杂度是 O(n·k)，而我需要 O(n)？
触发词： “window of size k”, “consecutive k elements”, “substring length k”
2. Sliding Window（可变大小）
提问这些问题：
- 窗口大小 不是固定的，而是受某个条件约束？
- 我是否在寻找满足条件的 最小 / 最大 subarray？
- 能否 向右扩展 并 向左收缩？
触发词： “at most k”, “at least k”, “minimum window”, “longest substring”
3. Two Pointers（同向）
提问这些问题：
- 我是否用两个索引 左 → 右 遍历数组？
- 是否有一个指针在追赶另一个指针？
- 我是否在维护数组内部的 range？
触发词： “subarray”, “range”, “continuous segment”
4. Two Pointers（相向）
提问这些问题：
- 数组是否 已排序？
- 我是否在寻找满足条件的 pair？
- 能否根据比较结果执行 left++ 或 right—？
触发词： “pair sum”, “target”, “sorted array”
5. Fast & Slow Pointers（环检测）
提问这些问题：
- 是否存在 linked list 或指针结构？
- 是否可能出现 cycle / loop？
- 能否让一个指针的移动速度是另一个的 2×？
触发词： “cycle”, “loop”, “circular”, “duplicate via index jump”
6. Prefix Sum
提问这些问题：
- 我是否需要 频繁求区间和？
- 题目是否涉及 subarray sum equals k？
- 累计的前缀和是否能帮助解题？
触发词： “range sum”, “subarray sum”, “sum between i and j”
7. Difference Array
提问这些问题：
- 是否有 多次区间更新？
- 我是否被要求对区间进行 增量/减量 操作？
- 最终值重要，中间过程不重要？
触发词： “range update”, “apply operations”, “add x from l to r”
8. Hash Map Frequency Counting
提问这些问题：
- 我是否在统计 元素/字符的频率？
- 是否需要 常数时间查找？
- 顺序是否不如 计数 重要？
触发词： “frequency”, “count occurrences”, “anagram”
9. In‑place Modification
提问这些问题：
- 题目是否要求 不使用额外空间？
- 能否直接修改原数组？
- 输出是否期望 在同一数组内部？
触发词： “in‑place”, “O(1) space”, “modify input”
10. Sorting‑based Pattern
提问这些问题：
- 排序后是否能大幅简化逻辑？
- 我是否在匹配 pair 或 interval？
- 改变顺序是否不影响正确性？
触发词： “after sorting”, “arrange”, “reorder”
11. Cyclic Sort
提问这些问题：
- 数字是否在范围 1…n 之内？
- 每个数字是否应该位于 特定索引？
- 我是否在寻找 缺失 / 重复 元素？
触发词： “missing number”, “duplicate”, “1 to n”
12. Kadane’s Algorithm（最大子数组）
提问这些问题：
- 是否要求 maximum sum subarray？
- 负数和是否会导致问题？
- 当累计和 n/2 次时是否可以重置？
- 是否可以假设 majority 存在？
- 是否需要 O(1) space？
触发词： “majority element”, “more than half”
20. Reservoir Sampling
提问这些问题：
- 数据是否 流式 / 无限？
- 是否事先不知道
n的大小？ - 是否需要 均匀随机抽样？
触发词： “stream”, “random sample”, “unknown size”