370 Range Addition

370. Range Addition​
1. Question
Assume you have an array of lengthninitialized with all0's and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarrayA [startIndex ... endIndex](startIndex and endIndex inclusive) with inc.
Return the modified array after allkoperations were executed.
Example:
1
Given:
2
    length = 5,
3
    updates = [
4
        [1,  3,  2],
5
        [2,  4,  3],
6
        [0,  2, -2]
7
    ]
8
​
9
Output:
10
    [-2, 0, 3, 5, 3]
Copied!
Explanation:
1
Initial state:
2
[ 0, 0, 0, 0, 0 ]
3
​
4
After applying operation [1, 3, 2]:
5
[ 0, 2, 2, 2, 0 ]
6
​
7
After applying operation [2, 4, 3]:
8
[ 0, 2, 5, 5, 3 ]
9
​
10
After applying operation [0, 2, -2]:
11
[-2, 0, 3, 5, 3 ]
Copied!
2. Implementation
思路: https://leetcode.com/problems/range-addition/discuss/84225/Detailed-explanation-if-you-don't-understand-especially-%22put-negative-inc-at-endIndex+1%22​
1
class Solution {
2
    public int[] getModifiedArray(int length, int[][] updates) {
3
        int[] res = new int[length];
4
​
5
        for (int[] update : updates) {
6
            int start = update[0];
7
            int end = update[1];
8
            int value = update[2];
9
​
10
            res[start] += value;
11
            if (end + 1 < length) {
12
                res[end + 1] -= value;
13
            }
14
        }
15
​
16
        for (int i = 1; i < length; i++) {
17
            res[i] += res[i - 1];
18
        }
19
        return res;
20
    }
21
}
Copied!
3. Time & Space Complexity
时间复杂度O(n + k), 空间复杂度O(n)

406 Queue Reconstruction by Height

415 Add Strings

Last modified 2yr ago

Copy link

Contents

370. Range Addition

1. Question

2. Implementation

3. Time & Space Complexity

370. Range Addition​

1. Question

2. Implementation

3. Time & Space Complexity

370. Range Addition