LeetCode 370 Range Addition

LeetCode

You are given an integer length and an array updates where updates[i] = [startIdx<sub>i</sub>, endIdx<sub>i</sub>, inc<sub>i</sub>].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the i<sup>th</sup> operation, you should increment all the elements arr[startIdx<sub>i</sub>], arr[startIdx<sub>i</sub> + 1], ..., arr[endIdx<sub>i</sub>] by inc<sub>i</sub>.

Return arr after applying all the updates.

Example 1:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]

Constraints:

1 <= length <= 10<sup>5</sup> 0 <= updates.length <= 10<sup>4</sup>
0 <= startIdx<sub>i</sub> <= endIdx<sub>i</sub> < length -1000 <= inc<sub>i</sub> <= 1000

题目大意：

统一加一个数到子数组中，如此有好几个操作，求最后数组结果

解题思路：

差分数组，数加到首节点，数减在末节点 + 1，最后累加

解题步骤：

N/A

注意事项：

1. 数加到首节点，数减在末节点 + 1，最后累加
2. 端点需要累加res[li[0]] += li[2], 而不是res[li[0]] = li[2]
3. len(res)而不是len(li)

Python代码：

def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
	res = [0] * length
	for li in updates:
		res[li[0]] += li[2] # remember += not =
		if li[1] + 1 < len(res): # remember not len(li)
			res[li[1] + 1] += -li[2] # remember += not =
	for i in range(1, len(res)):
		res[i] += res[i - 1]
	return res

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1), n, m分别为数组长度和update个数