370.区间加法

370.区间加法

题目大意:给一个二维数组,其中每个数组长度为3,包含了更新信息.

一、直接法

解题思路:硬算即可.

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> res(length);
        for (auto u : updates) {
            for (int i = u[0]; i <= u[1]; i++) {
                res[i] += u[2];
            }
        }
        return res;
    }
};

二、差分数组

这才是本题要考察的方法，差分数组算法参考https://labuladong.gitee.io/algo/2/21/52/

简单来说用一个diff数组记录nums前后元素的差值，即diff[i] = nums[i] - nums[i-1], i >= 1，当nums的i~j区间整体加x（某个数）时，i~j区间diff是不变的，只有两端的diff改变，利用这个性质减少运算量，最后再用nums[i] = nums[i-1] + diff[i]还原

class Solution:
    def rangeAddition(self, length, updates):
        diff = [0] * length	 #差分数组，因为初始原数组全0，因此差分也是0
        #进入迭代
        for update in updates:
            i, j, val = update[0], update[1], update[2]
            diff[i] += val
            if j+1 < length:	#注意当j+1越界时的处理
                diff[j+1] -= val
        #迭代完成后还原数组
        res = [0] * length
        res[0] = diff[0]
        for i in range(1, length):
            res[i] = res[i-1] + diff[i]
        return res