统计隐藏数组数目

难度: Medium

给你一个下标从 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⁵

Submission

运行时间: 88 ms

内存: 30.0 MB

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        mx=mn=0
        arr=list(accumulate(differences))
        mn=min(0,min(arr))
        mx=max(0,max(arr))
        return upper-mx-(lower-mn)+1 if upper-mx-(lower-mn)+1>0  else 0

Explain

本题解首先通过累加 differences 数组得到一个新数组 arr，该数组代表从某个起始值开始的隐藏数组各个位置的相对变化。通过计算 arr 数组与初始值 0 的最大值和最小值，可以确定隐藏数组值的可能范围。接着，我们计算这个范围与给定的 lower 和 upper 之间是否有重叠，并计算这个重叠区间的大小。如果重叠区间的长度为正，则这就是符合条件的隐藏数组的数量；否则，返回 0。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        # 计算 differences 的累加和，形成 arr 数组
        arr = list(accumulate(differences))
        # 找出 arr 中的最小值（考虑从0开始的相对最小位置）
        mn = min(0, min(arr))
        # 找出 arr 中的最大值（考虑从0开始的相对最大位置）
        mx = max(0, max(arr))
        # 计算可能的起始值的范围，并检查这个范围是否正数
        count = upper - mx - (lower - mn) + 1
        # 如果计算出的范围大于0，返回这个值；否则返回0
        return count if count > 0 else 0

Explore

在本题中，differences 数组中的每个元素表示隐藏数组相邻元素之间的差值。通过将 differences 数组的元素累加，我们可以重构出隐藏数组相对于起始元素的每个位置的值。这个新数组 arr 不直接代表隐藏数组的绝对值，而是表示从起始元素开始的相对变化。这种重构是理解和计算隐藏数组在给定范围内可能的起始值的关键步骤。

在 arr 数组中包含 0 是因为 arr 数组是从某个未知的起始点开始计算的，而这个起始点是我们设为 0 的相对点。包括 0 的目的是确保在计算隐藏数组的可能起始值时能够考虑到整个数组的范围，包括起始点本身。这样我们就可以正确计算出隐藏数组的实际最小值和最大值，并据此推断出符合条件的起始值范围。

这个表达式是为了确定隐藏数组所有元素都在给定的 lower 和 upper 范围内的有效起始值的数量。给定 arr 数组中的最小值 mn 和最大值 mx，隐藏数组的起始值需要在一个特定的范围内才能确保整个数组的值都在 [lower, upper] 内。此范围由两部分确定：隐藏数组的最大值不能超过 upper，因此起始值最大为 `upper - mx`；隐藏数组的最小值不能低于 lower，因此起始值最小为 `lower - mn`。两者形成一个闭区间 `[lower - mn, upper - mx]`。`upper - mx - (lower - mn) + 1` 计算的是这个区间内整数的个数。

如果 differences 数组全为正或全为负，这意味着 arr 数组将呈现单调递增或单调递减的形态。这将直接影响到计算 mn 和 mx 时的结果，即 arr 数组的极端值将更加极端（更大或更小）。这种极端情况可能会导致计算出的起始值范围非常小或者没有有效的起始值（即范围内没有整数）。然而，解题逻辑仍然有效，因为它正确地处理了这种极端情况，即使结果可能是返回 0 个有效数组。