LC370.区间加法

image.png

思路：差分

  • 差分数组
  • 将原始数组视为差分数组的前缀和
  • nums[0] = diff[0]
  • num[i] = nums[i - 1] + diff[i]
  • 注意相加的区间

    代码

    ```c class Solution { public: vector getModifiedArray(int length, vector>& updates) {
    1.   int n = updates.size();
    2.   vector<int> diff(length + 1, 0);
    3.   for (int i = 0; i < n; ++i) {
    4.       int begin_pos = updates[i][0];
    5.       int end_pos = updates[i][1];
    6.       int num = updates[i][2];
    7.       diff[begin_pos] += num;
    8.       diff[end_pos + 1] -= num;
    9.   }
    vector<int> nums(length, 0);
    for (int i = 0; i < length; i++) {
        if (i == 0) {
            nums[0] = diff[0];
        } else {
            nums[i] = nums[i - 1] + diff[i];
        }
    }

    return nums;
}

}; ```