370. Range Addition.md

title	toc	date	tags	top
370. Range Addition	false	2017-10-30	Leetcode Array	370

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:

Given:
    length = 5,
    updates = [
        [1,  3,  2],
        [2,  4,  3],
        [0,  2, -2]
    ]
Output:
    [-2, 0, 3, 5, 3]
Explanation:
    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 ]

Hint:

• Thinking of using advanced data structures? You are thinking it too complicated.
• For each update operation, do you really need to update all elements between $i$ and $j$?
• Update only the first and end element is sufficient.
• The optimal time complexity is $O(k + n)$ and uses $O(1)$ extra space.

分析

LintCode链接。暴力法：每次更新[startIndex, endIndex]区间

public int[] getModifiedArray(int length, int[][] updates) {
    int[] res = new int[length];
    for (int i = 0; i < updates.length; i++)
        for (int j = updates[i][0]; j <= updates[i][1]; j++)
            res[j] += updates[i][2];
        
    return res;
}

比较巧妙的方法：

public int[] getModifiedArray(int length, int[][] updates) {
    int[] arr = new int[length + 1], res = new int[length];
    for (int[] update : updates) {
        arr[update[0]] += update[2];
        arr[update[1] + 1] -= update[2];
    }
    res[0] = arr[0];
    for (int i = 1; i < length; i++)
        res[i] = res[i - 1] + arr[i];
    return res;
}