LeetCode 370. 区间加法（差分思想）
LeetCode 370. 区间加法（差分思想）
Michael阿明
发布于 2020-07-13 14:48:30
发布于 2020-07-13 14:48:30
文章被收录于专栏：Michael阿明学习之路
1. 题目
假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。
请你返回 k 次操作后的数组。
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]
解释:
初始状态:
[0,0,0,0,0]
进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]
进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]
进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-addition 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目： LeetCode 1109. 航班预订统计（差分思想） LeetCode 1094. 拼车
- 左端点加上数字，右端点+1的位置 减去该数字
- 最后遍历求前缀和
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> ans(length, 0);
for(auto& u : updates)
{
ans[u[0]] += u[2];
if(u[1]+1 < length)
ans[u[1]+1] -= u[2];
}
for(int i = 1; i < length; ++i)
ans[i] += ans[i-1];
return ans;
}
};40 ms 14.1 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
