题目： 2772. 使数组中的所有元素都等于零

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。

你可以对数组执行下述操作任意次：

从数组中选出长度为 k 的任一子数组，并将子数组中每个元素都减去 1 。
如果你可以使数组中的所有元素都等于 0 ，返回 true ；否则，返回 false 。

子数组是数组中的一个非空连续元素序列。

示例 1：

输入：nums = [2,2,3,1,1,0], k = 3

输出：true

解释：可以执行下述操作：

选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [1,1,2,1,1,0]
选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,1,0,0,0]
选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [0,0,0,0,0,0]

示例 2：

输入：nums = [1,3,1,1], k = 2

输出：false

解释：无法使数组中的所有元素等于 0

提示：

1 <= k <= nums.length <= 105

0 <= nums[i] <= 106

分析

想一想，如果 nums[0]>0nums[0]>0，那么必须要执行什么样的操作？

对于 nums[0]>0 的情况，必须把 nums[0] 到nums[k−1] 都减去 nums[0]

然后思考 nums[1] 要怎么处理，依此类推。

子数组同时加上/减去一个数，非常适合用差分数组来维护。

什么是差分数组

比如我们现在有一个数组arr，arr={0,2,5,4,9,7,10,0}

那么差分数组是什么呢？其实差分数组本质上也是一个数组，我们暂且定义差分数组为d，差分数组d的大小和原来arr数组大小一样，而且di=arri-arri-1，且di=0，它的含义是什么？就是原来数组i位置上的元素和i-1位置上的元素作差，得到的值就是di的值。

那么构造了这么个玩意有什么用呢？难道是来浪费宝贵的内存空间的？嗯，确实是来浪费宝贵的内存了，但是却换了时间上的高效。

现在我们有这么一个区间修改操作，即在区间1~4上，所有的数值都加上3.

我们不要傻傻地遍历arr数组的1，4范围，然后再分别给每个值加上3，我们此时更改差分数组d即可。

显而易见，差分数组d在2，4范围内的值都不用改变，只需要改变差分数组位置1和位置5的值即可，即d1=d1+3，而d5=d5-3，其余不变，为什么呢？因为差分数组的定义——di=arri-arri-1

现在，我们如何根据差分数组d来推测arr中某一个位置的值呢？

比如，此时，我们想知道arr1的值，我们不能直接通过arr1得到原来的值，因为在区间修改的操作中我们并没有修改arr的值，因此我们必须从前往后遍历递推，由于d0=arr0-0(我们定义arr0的前一个数为0)，那么arr0=d0=0，又由于d1=arr1-arr0=5，那么arr1=5+arr0=5。以此类推，由于d2=arr2-arr1=3，所以arr2=3+arr1=8。

本意解答

设差分数组为 d。那么把 nums[i] 到 nums[i+k−1] 同时减去 1，等价于把 d[i] 减 d[i+k] 加 1。

注意子数组长度必须恰好等于 k，所以当 i+k≤n 时，才能执行上述操作。

遍历数组的同时，用变量 sumD 累加差分值。遍历到 nums[i] 时，nums[i]+sumD 就是 nums[i] 的实际值了。

分类讨论：

如果 nums[i]<0，由于无法让元素值增大，返回 false。
如果 nums[i]=0，无需操作，遍历下一个数。
如果 nums[i]>0：
- 如果 i+k>n，无法执行操作，所以 nums[i] 无法变成 0，返回 false。
- 如果 i+k≤n，按照上面说的执行操作，修改差分数组，遍历下一个数。

如果遍历中途没有返回 false，那么最后返回 true

代码

func CheckArray(nums []int, k int) bool {
   n := len(nums)
   d := make([]int, n+1)
   sum_d := 0
   for i := range nums {
      sum_d += d[i]
      nums[i] += sum_d
      if nums[i] == 0 {
         continue
      }
      if nums[i] < 0 || i+k > n {
         return false
      }
      // 将区间[i,i+k]的每个元素都减去nums[i]。等价于d[i]-=nums[i],d[i+k]-=nums[i]
      sum_d -= nums[i] // 等价于d[i]-=nums[i]，没有必要真的操作d[i]，因为已经用不到了
      d[i+k] += nums[i]
   }
   return true
}