数组总结

差分数组

算法介绍:https://labuladong.gitee.io/algo/2/21/52/

模板:370. Range Addition

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

类似题目:

1094.拼车

1109.航班预订统计

最后更新于