class Solution {
public:
int numberOfArrays(vector<int>& differences, int lower, int upper) {
}
};
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.length1 <= n <= 105-105 <= differences[i] <= 105-105 <= lower <= upper <= 105原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 54 MB, 提交时间: 2023-09-06 23:28:46
class Solution {
public int numberOfArrays(int[] differences, int lower, int upper) {
int x = 0, y = 0, cur = 0;
for (int d: differences) {
cur += d;
x = Math.min(x, cur);
y = Math.max(y, cur);
if (y - x > upper - lower) {
return 0;
}
}
return (upper - lower) - (y - x) + 1;
}
}
cpp 解法, 执行用时: 136 ms, 内存消耗: 103.9 MB, 提交时间: 2023-09-06 23:27:14
class Solution {
public:
int numberOfArrays(vector<int>& differences, int lower, int upper) {
int x = 0, y = 0, cur = 0;
for (int d: differences) {
cur += d;
x = min(x, cur);
y = max(y, cur);
if (y - x > upper - lower) {
return 0;
}
}
return (upper - lower) - (y - x) + 1;
}
};
python3 解法, 执行用时: 184 ms, 内存消耗: 29.9 MB, 提交时间: 2023-09-06 23:27:00
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
x = y = cur = 0
for d in differences:
cur += d
x = min(x, cur)
y = max(y, cur)
if y - x > upper - lower:
return 0
return (upper - lower) - (y - x) + 1
golang 解法, 执行用时: 120 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-06 23:26:21
func numberOfArrays(differences []int, lower, upper int) int {
num, min, max := 0, 0, 0 // 初始元素为 0
for _, d := range differences {
num += d // 根据差分数组还原原始数组的元素值 num
if num < min {
min = num
} else if num > max {
max = num
}
}
ans := upper - lower + 1 - (max - min)
if ans > 0 {
return ans
}
return 0
}