Appearance
数组、前缀和与区间
数组题先确认输入范围、是否有序、是否允许修改原数组，以及结果是否可能溢出。重点是写清循环不变量、边界与复杂度；需要特定标准库 API 时，跳转到对应的算法或 C++ 笔记。
数组与双指针
双指针的重点是先说明两个指针分别代表什么，以及哪条不变量决定指针移动：
- 相向双指针：常用于有序数组两数之和、盛水容器和回文判断；根据当前和或高度移动一端；
- 同向双指针：读写指针压缩数组，或维护快慢位置；
- 滑动窗口：维护区间
[left, right]及统计量，右端扩张，条件不满足或需要优化答案时收缩左端。
滑动窗口成立通常依赖可维护的单调性。例如正整数数组中“和至少为 target 的最短连续子数组”可用 O(n) 窗口；若数组含负数，窗口和不再随右端扩张单调增长，不能直接套模板，可能需要前缀和与单调队列。
原地压缩：移动零
使用读指针扫描、写指针写入非零元素，再把尾部补零，可保持非零元素相对顺序：
cpp
void move_zeroes(std::vector<int>& nums) {
std::size_t write = 0;
for (int value : nums) {
if (value != 0) nums[write++] = value;
}
std::fill(nums.begin() + write, nums.end(), 0);
}时间 O(n)、额外空间 O(1)。
前缀和与差分
前缀和适用于频繁查询静态区间和：
text
prefix[0] = 0
prefix[i + 1] = prefix[i] + nums[i]
sum(l, r) = prefix[r + 1] - prefix[l]差分数组适用于大量区间加法、最后统一还原。对闭区间 [left, right] 加 value：
cpp
diff[left] += value;
if (right + 1 < n) diff[right + 1] -= value;随后对 diff 做一次前缀和即可得到每个位置的最终值。航班预订统计和时间段并发计数都是该模式；时间边界是否“登出时仍在线”必须先定义清楚。
区间题
区间题通常先排序，再维护已选择/合并区间的右边界：
- 合并区间：按左端点升序，重叠时扩展当前右端点；
- 最多不重叠区间：按右端点升序，尽早结束以给后续保留空间；
- 最少箭数：按端点排序后维护当前公共交集的最小右端点。
比较器应使用 const 引用并满足严格弱序：
cpp
std::sort(intervals.begin(), intervals.end(),
[](const auto& a, const auto& b) {
return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
});复杂度速查
| 操作 | 典型复杂度 |
|---|---|
| 遍历、双指针、前缀和构建 | O(n) |
| 差分更新后统一还原 | O(n) |
| 已排序序列二分 | O(log n) |
| 区间排序 + 单次扫描 | O(n log n) |