LeetCode 370. 区间加法

2023-05-01 HGNULB 约 4 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 370. 区间加法

题意分析

题目目标：给定一个长度为 length、初始全为 0 的数组，以及若干条形如 [startIndex, endIndex, inc] 的操作，每条操作把闭区间内的每个元素都加上 inc，要求返回所有操作执行完之后的最终数组。
核心约束：所有操作是一次性给全的，题目只问最终状态，中途不需要查询任何一个下标的值——这条「离线 + 只要终态」的性质是最大的信号，说明可以打乱执行顺序、也可以把每条操作压缩成常数个标记，最后统一还原。另一个信号是操作作用于连续区间且是加法，加法可交换可结合，因此区间的影响可以被拆成「从某处开始生效、到某处失效」两个端点事件。
边界处理：endIndex 可能正好等于 length-1，此时「失效点」落在数组之外，必须让辅助数组多留一格或显式判断越界；同一区间可能被多次更新，累加不能覆盖；length 可能为 1，updates 也可能为空，此时应返回全 0 数组而不是空数组。

解法：差分数组

核心思路

每条更新对闭区间 [left,right] 增加同一个值。用差分数组记录增量的变化：在 left 处开始生效，在 right+1 处失效，因此只需执行 diff[left] += inc、diff[right+1] -= inc。

不变量：处理任意数量的更新后，diff[i] 等于最终数组在 i 处相对前一位置的增量变化，约定位置 -1 的值为 0。于是从左到右求 diff 的前缀和，就能恢复每个位置应获得的总增量。

正确性：单次更新的两个端点标记在前缀累加后，恰好让 [left,right] 内增加 inc、其他位置不变。多条更新的标记可按加法叠加；前缀和对叠加结果线性恢复，因此得到所有操作后的最终数组。

解题步骤

创建长度为 length+1 的差分数组，使末尾区间的 right+1 仍可安全写入。

对每条更新累加两个端点标记，不能用赋值覆盖已有更新。

只扫描前 length 个差分值并累计，依次写入结果数组。

length=5、更新为 [[1,3,2],[2,4,3],[0,2,-2]] 时，端点叠加后求前缀和得到 [-2,0,3,5,3]。

边界 [0,length-1,inc] 的失效点正好是哨兵下标 length，不会影响返回数组，也无需额外分支。

代码实现

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(n+q)$，q 条更新各做常数次操作，最后扫描长度 n 的数组。

空间复杂度：$O(n)$，用于差分数组和返回结果。

关键点总结

离线区间加法只需记录“开始生效”和“停止生效”两个事件。

闭区间的停止位置是 right+1，不是 right。

多条更新在端点上必须累加，操作顺序不影响最终结果。

差分记录变化，前缀和恢复值，两者互为逆过程。

易错点总结

在 diff[right] 处减：[0,1,5] 会漏掉右端点，得到 [5,0,0] 而非 [5,5,0]。

差分只开 length 却无条件写 right+1：覆盖末尾的更新会数组越界。

端点使用赋值：重叠更新会覆盖先前标记，应使用 +=、-=。

返回 diff 而不求前缀和：区间内部的持续增量不会恢复。

忽略负增量：[[0,1,-3]] 的正确结果是 [-3,-3]。

相似题目

题目	难度	考察点
1109. 航班预订统计	中等	同样是区间加法，但下标从 1 开始，考察下标偏移与差分端点的换算
1094. 拼车	中等	差分之后还要在前缀和过程中随时判断是否超载，多了一层可行性校验
303. 区域和检索 - 数组不可变	简单	差分的逆问题：数组不变而区间查询频繁，改用前缀和预处理
560. 和为 K 的子数组	中等	前缀和配合哈希表统计满足条件的区间数，重点从区间更新转向区间求值
732. 我的日程安排表 III	困难	区间加法必须在线响应，无法离线结算，只能用有序表或线段树维护最大重叠层数