原题链接直达

1. 题目描述

给你一个下标从 0 开始且长度为 n 的整数数组 differences ，

它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。

更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。

同时给你两个整数 lower 和 upper ，它

们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。

比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，

那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。

[3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。

[5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。

[1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。

请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。

示例 1：

输入：differences = [1,-3,4], lower = 1, upper = 6

输出：2

解释：符合要求的隐藏数组为：

- [3, 4, 1, 5]

- [4, 5, 2, 6]

所以返回 2 。

示例 2：

输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5

输出：4

解释：符合要求的隐藏数组为：

- [-3, 0, -4, 1, 2, 0]

- [-2, 1, -3, 2, 3, 1]

- [-1, 2, -2, 3, 4, 2]

- [0, 3, -1, 4, 5, 3]

所以返回 4 。

示例 3：

输入：differences = [4,-7,2], lower = 3, upper = 6

输出：0

解释：没有符合要求的隐藏数组，所以返回 0 。

提示：

• n == differences.length

• 1 <= n <= 10⁵

• -10⁵ <= differences[i] <= 10⁵

• -10⁵ <= lower <= upper <= 10⁵

2. 分析

核心思路：数学分析+前缀和降维。

由于diff[i] = hidden[i+1] - hidden[i] => hidden[i+1] = diff[i] + hidden[i]

所以只要确定hidden[0] 就能确定所有的hidden元素。

1.朴素暴力

令 lower <= hidden[0] <= upper

检查生成的每一个hidden是否合法, for range hidden, 每次检查时间复杂度O(n)

k = upper-lower

时间复杂度：O(nk)

2.想办法降维（前缀和）

a:数学推导，尽量控制可变，以diff数组来表示hidden[i]元素

hidden[i+1] = diff[i] + hidden[i]

hidden[i] = diff[i-1] + hidden[i-1]

hidden[i-1] = diff[i-2] + hidden[i-2]

..

hidden[1] + hidden[2] + ... + hidden[i+1] = (diff[0] + ... diff[i]) + (hidden[0]+...hidden[i])

合并同类项：

=>

hidden[i+1] - hidden[0] = prefixSumdiff[i]

hidden[i+1] = hidden[0] + prefixSumdiff[i]

由此，我们将hidden[i+1]转为为了一个定量hidden[0]和diff的前缀和数组表达式。

b:由上述推导可知，想要确定hidden的所有元素是否都在lower和upper之间，我们只需要知晓diff前缀和的最小值和最大值，加hidden[0], 判断是否符合条件即可。

3. 代码实现

func numberOfArrays(differences []int, lower int, upper int) int {
    n := len(differences)
    sum := differences[0]
    minPreSumDiff, maxPreSumDiff := sum, sum
    for i := 1; i < n; i++ {
        sum += differences[i]
        minPreSumDiff = min(minPreSumDiff, sum)
        maxPreSumDiff = max(maxPreSumDiff, sum)
    }
    ans := 0
    // 枚举hidden0
    for hidden0 := lower; hidden0 <= upper; hidden0++ {
        // hidden[0]+minPresumDiff <= (hidden[i+1]==hidden[0]+presum[i]) <= hidden[0]+maxPreSumDiff
        if hidden0+maxPreSumDiff <= upper && hidden0+minPreSumDiff >= lower {
            ans++
        }
    }
    return ans
}