LeetCode 370. 区间加法
题目描述
题意分析
长度为
length的数组初始全为零，每条操作(left,right,inc)将闭区间[left,right]中的每个元素增加inc。操作可以重叠，增量也可以为负数，需要返回所有操作叠加后的结果。本文未保留完整原题约束，以下按现有接口的实现约定说明：操作端点满足
0 <= left <= right < length，差分标记及累计结果均能由代码中的int保存，不另行推定输入的数值上界。
解法：差分数组
核心思路
[!blue]
逐项修改每个区间，会反复访问重叠部分。可以先记录增量在哪个位置开始、在哪个位置结束，等全部操作处理完后再统一恢复数组。
设差分
diff[i]表示当前位置相对于前一位置的变化，初始数组全零，所以差分也全零。对[left,right]加inc后，区间内部相邻两项都增加相同值，相互的差不变；只有左端从这里开始多出inc，右端后一位从这里开始不再享受增量。因此只需diff[left] += inc、diff[right+1] -= inc。最后从左到右求差分的前缀和。对任意一次操作，在左端之前尚未累加其开始标记，贡献为零；在区间内只累加了
+inc，贡献为inc；越过右端后再累加-inc，贡献归零。所有操作的标记相加，就得到每个位置受到的总增量。差分多开一位，专门容纳覆盖末尾时写入
diff[length]的停止标记。这个位置不属于结果数组，恢复时只扫描前length项，不会多返回一个元素。
解题步骤
- 创建长度为
length+1的零值差分数组。- 对每条操作，在左端累加
inc，在右端后一位累加-inc；同一位置已有的标记不能覆盖。- 令累计值
sum = 0，依次加上diff[i]，将当前累计值写入res[i]。- 扫描到
length-1后返回结果。没有任何操作时，差分始终为零，结果也自然全零。
代码实现
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] diff = new int[length + 1];
for (int[] u : updates) {
int l = u[0];
int r = u[1];
int inc = u[2];
// 左端开始生效，右端后一位抵消，多个操作累加。
diff[l] += inc;
diff[r + 1] -= inc;
}
int[] res = new int[length];
int sum = 0;
for (int i = 0; i < length; i++) {
// 前缀累计恢复当前下标受到的全部增量。
sum += diff[i];
res[i] = sum;
}
return res;
}
}
func getModifiedArray(length int, updates [][]int) []int {
diff := make([]int, length+1)
for _, u := range updates {
l, r, inc := u[0], u[1], u[2]
// 左端开始生效，右端后一位抵消，多个操作累加。
diff[l] += inc
diff[r+1] -= inc
}
res := make([]int, length)
sum := 0
for i := 0; i < length; i++ {
// 前缀累计恢复当前下标受到的全部增量。
sum += diff[i]
res[i] = sum
}
return res
}
复杂度分析
- 时间复杂度：$O(length+q)$，其中 $q$ 是操作数。每条操作只写两个标记，之后线性恢复结果。
- 空间复杂度：不计返回结果为 $O(length)$，用于差分数组；结果另占 $O(length)$。
关键点总结
[!green]
- 闭区间在 right+1 停止生效。
- 同一端点的多次影响必须累加。
- 差分保存变化，前缀和恢复最终值。
易错点总结
[!yellow]
- 在 right 处减 inc：漏掉右端点。
- 端点直接赋值：覆盖之前的操作影响。
- 直接返回差分：尚未恢复区间内部的持续增量。
- 少开一位却无条件写 right+1：操作覆盖末尾时会越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1109. 航班预订统计 | 中等 | 同样用区间起点加、终点后一位减表示批量增加，最后前缀还原各位置值。 |
| 1094. 拼车 | 中等 | 同样把区间贡献变成起止事件，原题扫描累计人数是否超过容量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！