LeetCode 题解工作台
统计隐藏数组数目
给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。 同时…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 前缀和
答案摘要
由于数组 已经确定，那么数组 的元素最大值与最小值之差也是固定的，我们只要确保差值不超过 $\textit{upper} - \textit{lower}$ 即可。 我们不妨假设数组 的第一个元素为 ，那么 $\textit{hidden}[i] = \textit{hidden}[i - 1] + \textit{differences}[i - 1]$，其中 $1 \leq i \leq…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 前缀和 题型思路
题目描述
给你一个下标从 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
解题思路
方法一：前缀和
由于数组 已经确定，那么数组 的元素最大值与最小值之差也是固定的，我们只要确保差值不超过 即可。
我们不妨假设数组 的第一个元素为 ，那么 ，其中 。记数组 的最大值为 ，最小值为 ，如果 ，那么我们就可以构造出一个合法的 数组，可以构造的个数为 。否则，无法构造出合法的 数组，返回 。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
x = mi = mx = 0
for d in differences:
x += d
mi = min(mi, x)
mx = max(mx, x)
return max(upper - lower - (mx - mi) + 1, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Understanding prefix sum calculation is crucial to solving this problem.
- question_mark
Candidates should handle range filtering effectively to ensure correct sequences.
- question_mark
Watch for solutions that improperly iterate or recompute values multiple times.
常见陷阱
外企场景- error
Failing to correctly compute the subsequent sequence values based on the first fixed value.
- error
Not accounting for sequences where any value exceeds the specified range.
- error
Using an inefficient approach that leads to higher time complexity than O(n).
进阶变体
外企场景- arrow_right_alt
Consider extending this problem to support different types of sequences, such as geometric sequences.
- arrow_right_alt
What if the sequence is not constrained by a fixed range? How would that change the solution?
- arrow_right_alt
Modify the problem to account for sequences with additional constraints, such as specific values at certain indices.