数组相关算法

数组算法的本质只围绕4件事

1. 下标移动（指针）
2. 区间的维护
3. 状态的积累/更新
4. 空间换时间（辅助数组/哈希）

所有的数组题，几乎都能归到下面几种套路之一

排序算法在数组上的应用

双指针(Two Pointers)

思想：用两个下表在数组上移动，减少时间复杂度

常见场景

• 有序数组去重
• 两数之和（有序）
• 反转数组
• 原地删除元素

本质：用覆盖代替删除

滑动窗口（Sliding Window）

思想：维护一个[l, r)区间，动态扩张/收缩

常见问题

• 最长/最短子数组
• 连续子数组满足条件
• 字符串相关问题

本质：区间 + 状态维护

前缀和（Prefix Sum）

思想：吧区间求和变成O(1)

sum[i] = a[0] + a[1] + ... + a[i - 1]

常见问题

• 区间和查询
• 子数组和等于k
• 二维数组求和

本质：用空间换时间

差分数组（Difference Array）

思想：高效处理“区间修改”

diff[l] += x
diff[r+1] -= x

常见问题

• 多次区间加减
• 批量更新

本质：反向思维：改区间，不改单点

排序 + 扫描

思想：先排序，再用线性扫描解决复杂问题

常见问题

• 区间合并
• 三数之和
• 最小差值问题

本质：无序 -> 有序

单调栈（数组进阶）

思想：维护一个“单调”的栈（递增/递减）

常见问题

• 下一个更大元素
• 最大矩形
• 接雨水

本质：一次遍历，找到左右边界

二分查找(Binary Search)

思想：不是只查数，而是查边界

常见问题

• 查找第一个/最后一个满足条件的位置
• 在答案空间上二分（不是数组）

本质：有序 + 判定函数