ID | Title | Difficulty | |
---|---|---|---|
Loading... |
370. Range Addition
Medium
LeetCode
Array, Prefix Sum
Problem
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:
Input: 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]
Code
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] res = new int[length];
for(int[] update : updates) {
res[update[0]] += update[2];
if(update[1] < length - 1) {
res[update[1] + 1] -= update[2];
}
}
int curr = res[0];
for(int i = 1; i < length; i++) {
res[i] += curr;
curr = res[i];
}
return res;
}
}
按 <- 键看上一题!
369. Plus One Linked List
按 -> 键看下一题!
371. Sum of Two Integers