【LeetCode】370. Range Addition 解题报告(C++)

时间:2024-09-28 21:05:08

题目地址:https://leetcode-cn.com/problems/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.

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]

题目大意

假设你有一个长度为 n 的数组,初始情况下所有的数字均为 0,你将会被给出 k​个更新的操作。
其中,每个操作会被表示为一个三元组:[startIndex, endIndex, inc],你需要将子数组 A[startIndex … endIndex](包括 startIndex 和 endIndex)增加 inc。
请你返回 k 次操作后的数组。

解题方法

只修改区间起终点

我第一次做的时候,把[start,end]区间内的所有元素进行了遍历修改,会导致超时。

看了官方解答之后明白,哦,原来只用修改起始位置和结束位置就行了,让区间起点+=inc,区间终点-=inc,区间中间的部分暂时不用更新。最后从左到右再遍历一次,累计求和并修改每个位置的值。

总的时间复杂度是O(N + k),空间复杂度是O(1).

C++代码如下:

class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> res(length, 0);
for (auto& up : updates) {
int start = up[0], end = up[1], inc = up[2];
res[start] += inc;
if (end < length - 1)
res[end + 1] -= inc;
}
int cursum = 0;
for (int i = 0; i < length; ++i) {
cursum += res[i];
res[i] = cursum;
}
return res;
}
};

参考资料:https://leetcode-cn.com/problems/range-addition/solution/qu-jian-jia-fa-by-leetcode/

日期

2019 年 9 月 18 日 —— 今日又是九一八