370. Range Addition

发表于 | 分类于

Assume you have an array of length n initialized with all 0’s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Given:
    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]
Output:
    [-2, 0, 3, 5, 3]

Explanation:

1
2
3
4
5
6
7
8
9
10
11
Initial state:
[ 0, 0, 0, 0, 0 ]
After applying operation [1, 3, 2]:
[ 0, 2, 2, 2, 0 ]
After applying operation [2, 4, 3]:
[ 0, 2, 5, 5, 3 ]
After applying operation [0, 2, -2]:
[-2, 0, 3, 5, 3 ]

解法1： O(n) + O(k)

这题如果用一般的办法会TLE。关键的点在于不用更新start和end之间所有的数。那么我们只更新start的数，意思是从这往后所有的数都要加上start对应的数字。同时需要在end+1的地方减去increment，意思是从这里往后所有的数要减去start对应的数字，以此来抵消多加的那一份。
最后我们在遍历一遍数组，做一个累加就得到了结果。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        if (length <= 0) {
            return new int[0];
        }
        int[] res = new int[length];
        for (int i = 0; i < updates.length; i++) {
            res[updates[i][0]] += updates[i][2];
            if (updates[i][1] < res.length - 1) {
                res[updates[i][1] + 1] -= updates[i][2];
            }
        }
        for (int i = 1; i < res.length; i++) {
            res[i] += res[i - 1];
        }
        return res;
    }
}