leetcode 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.
原题地址

Google OA题。思路就是先把每一步的操作加、减到开始、结束位，最后累积求和。
不知道为什么速度不是很快，代码如下：

1
2
3
4
5
6
7
8
9
10
11

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> re(length + 1, 0);
    for (vector<int> & vec: updates) {
        re[vec[0]] += vec[2];
        re[vec[1] + 1] -= vec[2];
    }
    re.pop_back();
    for (int i = 1; i < length; i++)
        re[i] += re[i - 1];
    return re;        
}