力扣2145. 统计隐藏数组数目

给你一个下标从 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 <= 105
    -105 <= differences[i] <= 105
    -105 <= lower <= upper <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-the-hidden-sequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

很容易就能明白，总共有多少中解是由隐藏数组中的最大值和最小值与lower以及supper作比较得出的。

可以先假设隐藏数组的首数字是0，通过遍历differences数组来求出隐藏数组中的所有数字，利用额外变量min和max存储隐藏数组中的最大值和最小值，最后与lower和supper做比较即可得出结果。

需要注意的是：无解判断为：max - min > lower - supper，此时直接返回0即可。

代码如下：

 1 class Solution {
 2     public int numberOfArrays(int[] differences, int lower, int upper) {
 3         //假设初始值为0，记录隐藏数组中的所有值
 4         int a = 0;
 5         //保存隐藏数组中的最小值
 6         int min = 0;
 7         //保存隐藏数组中的最大值
 8         int max = 0;
 9         //差值
10         int t = upper - lower;
11         for (int i : differences) {
12             //隐藏数组中，a之后的解，为了省空间，直接用a存储即可。
13             a += i;
14             min = Math.min(min, a);
15             max = Math.max(max, a);
16             //不存在解的情况下直接返回0
17             if (max - min > t) {
18                 return 0;
19             }
20         }
21         return t - (max - min) + 1;
22     }
23 }

运行结果如下：