leetcode：370. 区间加法

题目来源

• leetcode：370. 区间加法-vip

题目描述

class Solution {
    
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    
      
    }
};

题目解析

差分数组

要对一个区间多次增减，然后返回原数据变成什么样子时，用算法：差分数组最简单

class Solution {
    
    class Difference{
    
        std::vector<int> diff;
    public:
        explicit Difference(int length){
    
            diff.resize(length);
            for (int i = 0; i < length; ++i) {
    
                diff[i] = 0;
            }
        }

        void update(int i, int j, int val){
    
            diff[i] += val;
            if(j + 1 < diff.size()){
    
                diff[j + 1] -= val;
            }
        }

        std::vector<int> result(){
    
            int N = diff.size();
            std::vector<int> res(N, 0);
            res[0] = diff[0];
            for (int i = 1; i < N; ++i) {
    
                // diff[i] = res[i] - res[i - 1]---> res[i] = diff[i] + res[i - 1]
                res[i] = diff[i] + res[i - 1];
            }
            return res;
        }
    };
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    
        Difference d(length);
        for(auto arr : updates){
    
            d.update(arr[0], arr[1], arr[2]);
        }
        return d.result();
    }
};



int main() {
    
    vector<vector<int>> positions  {
    {
    1, 3, 2}, {
    2, 4, 3}, {
    0, 2, -2}};
    Solution a;
    auto ans = a.getModifiedArray(5, positions);
    for(auto i : ans){
    
        printf("%d\t", i);
    }
    return 0;
}