LeetCode刷题实战370：区间加法 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 区间加法，我们先来看题面：

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.

假设你有一个长度为 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]

解题

创建一个 int[] 数组 ans，长度为 length。

对于每一个给定的 [startIndex, endIndex, inc] 我们可以理解成如下：

把 ans 的 [startIndex,length-1] 都加上了 inc，然后再把 [endIndex+1, length-1] 再减去 inc。

具体的操作是：

1、先 ans[startIndex] += val，ans[endIndex+1] += -val；

2、然后 [startIndex,length-1] 遍历进行 ans[i] += ans[i-1]。

这样做的目的是因为所有的三元组 [startIndex, endIndex, inc] 对数组 ans 的操作是独立的，我们先对所有的三元组对 ans 的操作在边界上做好，然后遍历一遍 ans 数组即可同时执行完所有三元组对 ans 的操作。

class Solution {
   public int[] getModifiedArray(int length, int[][] updates) {
        int[] ans = new int[length];
        int start, end, val;
        for (int[] update : updates) {
            start = update[0];
            end = update[1];
            val = update[2];
            ans[start] += val;
            if (end < length - 1) {
                ans[end + 1] -= val;
            }
        }
        for (int i = 1; i < length; i++) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }
}