370. Range-Addition.md

题目

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

思路

示例的计算过程如下：

代码

class Solution(object):
    def getModifiedArray(self, length, updates):
        """
        :type length: int
        :type updates: List[List[int]]
        :rtype: List[int]
        """
        res = [0] * (length + 1)
        for item in updates:
            start, end, add_value = item[0], item[1], item[2]
            res[start] += add_value
            res[end + 1] -= add_value

        for i in range(1, length + 1):
            res[i] += res[i - 1]
        return res[:-1]


print(Solution().getModifiedArray(5,
                                  [[1, 3, 2], [2, 4, 3], [0, 2, -2]]))

---

注释版的代码：

class Solution():
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
            ans = [0] * (length + 1)
            for update in updates:
                ans[update[0]] += update[2] #从这个索引开始，后面的所有元素都将会被增加update[2]
                ans[update[1]+1] -= update[2] #但是，不在这一区间的元素本不应该被增加update[2]，所以这一区间之后的元素都设置会被减去update[2]
            for k in range(1, length):
                ans[k] += ans[k-1] #把上面的设置累加起来
            return ans[:length] #最后一个元素只是辅助的


# 链接：https://leetcode-cn.com/problems/range-addition/solution/ji-lu-yu-lei-jia-by-1050669722/

---

附：发现用golang协程的暴力解法，真是人才!

func getModifiedArray(length int, updates [][]int) []int {
  res:= make([]int, length);

  var wg sync.WaitGroup
  wg.Add(len(updates))
  for idx:=range updates{
      go func(index int){
          defer wg.Done()
          s:= updates[index][0]
          e:=updates[index][1];
          c:= updates[index][2];

          for i:=s;i<=e; i++{
              res[i]+=c;
          }
      }(idx)
  }

  wg.Wait();

  return res
}