1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        TreeMap<Integer, Integer> idxUpdate = new TreeMap<>();
        for (int[] update : updates) {
            idxUpdate.put(update[0], idxUpdate.getOrDefault(update[0], 0) + update[2]);
            idxUpdate.put(update[1] + 1, idxUpdate.getOrDefault(update[1] + 1, 0) - update[2]);
        }
        int[] ans = new int[length];
        int sum = 0;
        // updates是在给sum加成, 我们记录什么时候有加成, 什么时候停止加成, 不同的加成可以叠加.
        for (int i = 0; i < ans.length; i++) {
            sum += idxUpdate.getOrDefault(i, 0);
            ans[i] = sum;
        }
        return ans;
    }
}

sum记录叠加的值. 我们在叠加开始的地方去标记以及叠加结束的地方去标记. 这样我们知道什么时候给sum加成, 什么时候给sum减去加成.

时间复杂度: O(n + k)
空间复杂度: O(n) 因为存答案需要一个数组.