2145.统计隐藏数组数目

prefix sum, https://leetcode.cn/problems/count-the-hidden-sequences/

给你一个下标从 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^5
-10^5 <= differences[i] <= 10^5
-10^5 <= lower <= upper <= 10^5

只要找出hidden[0]的范围就可以

python

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        # 计算前缀差值的最小值和最大值
        cur = 0
        min_p = 0
        max_p = 0
        for d in differences:
            cur += d
            min_p = min(min_p, cur)
            max_p = max(max_p, cur)
        # 隐藏数组首元素 hidden[0] 的取值范围为 [lower - min_p, upper - max_p]
        low = lower - min_p
        high = upper - max_p
        # 返回可选的整数个数
        return max(0, high - low + 1)

这个题的核心点就在于：只要确定了 hidden[0] 的取值范围，就能唯一确定整个隐藏数组。

因为你有了 differences 数组，它描述的是相邻元素的差值，那么：

python

hidden[1] = hidden[0] + differences[0]
hidden[2] = hidden[1] + differences[1] = hidden[0] + differences[0] + differences[1]
...
hidden[i] = hidden[0] + prefix_sum[i - 1]

所以，整个隐藏数组都可以通过 hidden[0] 推导出来。

那怎么保证推导出来的 hidden 数组所有元素都在 [lower, upper] 范围内？

我们只需要保证：

python

lower <= hidden[i] = hidden[0] + prefix_sum[i-1] <= upper

把所有可能的偏移量 prefix_sum[i] 计算一遍，找出它的最小值 min_p 和最大值 max_p：

然后就可以解出隐藏数组第一个元素的范围：

python

lower <= hidden[0] + min_p      →   hidden[0] >= lower - min_p
upper >= hidden[0] + max_p      →   hidden[0] <= upper - max_p

所以合法的 hidden[0] 取值范围是：

python

[lower - min_p, upper - max_p]

这两个区间有重叠的部分就是合法的 hidden[0] 取值区间。

总结：

differences 确定了整个隐藏数组的差值结构；
只需要枚举合法的 hidden[0]；
每一个合法的 hidden[0] 对应一个完整的合法数组。

你用数学方式框定 hidden[0] 的范围，效率就极高，时间复杂度 O(n)。

有没有感觉这题其实是“差分数组”的逆操作？😄

2145.统计隐藏数组数目 ​

2145.统计隐藏数组数目