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：

输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0

提示：

  • n == differences.length
  • 1 <= n <= 10^5
  • -10^5 <= differences[i] <= 10^5
  • -10^5 <= lower <= upper <= 10^5

解题思路

解题思路

这道题的关键在于理解隐藏序列的性质。设隐藏序列的第一个元素为 x，那么整个序列就被唯一确定了：

  • hidden[0] = x
  • hidden[1] = x + differences[0]
  • hidden[2] = x + differences[0] + differences[1]
  • …

我们可以通过前缀和来计算隐藏序列相对于第一个元素的偏移量。

核心观察：

  1. 无论第一个元素 x 取什么值，隐藏序列中最大值和最小值的差（序列的"跨度"）是固定的
  2. 序列的跨度 = max_offset - min_offset
  3. 只要这个跨度能放入 [lower, upper] 区间，就存在有效的隐藏序列

算法步骤：

  1. 计算前缀和数组，得到每个位置相对于第一个元素的偏移量
  2. 找出偏移量的最大值和最小值
  3. 计算序列的跨度 = max_offset - min_offset
  4. 如果跨度 > (upper - lower)，则无解，返回 0
  5. 否则，可能的第一个元素的取值范围是 [lower - min_offset, upper - max_offset]
  6. 答案就是这个范围的长度

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long long prefix = 0;
        long long minVal = 0, maxVal = 0;
        
        for (int diff : differences) {
            prefix += diff;
            minVal = min(minVal, prefix);
            maxVal = max(maxVal, prefix);
        }
        
        long long range = maxVal - minVal;
        long long available = upper - lower;
        
        if (range > available) {
            return 0;
        }
        
        return (int)(available - range + 1);
    }
};

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        prefix = 0
        min_val = max_val = 0
        
        for diff in differences:
            prefix += diff
            min_val = min(min_val, prefix)
            max_val = max(max_val, prefix)
        
        range_span = max_val - min_val
        available = upper - lower
        
        if range_span > available:
            return 0
        
        return available - range_span + 1

public class Solution {
    public int NumberOfArrays(int[] differences, int lower, int upper) {
        long prefix = 0;
        long minVal = 0, maxVal = 0;
        
        foreach (int diff in differences) {
            prefix += diff;
            minVal = Math.Min(minVal, prefix);
            maxVal = Math.Max(maxVal, prefix);
        }
        
        long range = maxVal - minVal;
        long available = upper - lower;
        
        if (range > available) {
            return 0;
        }
        
        return (int)(available - range + 1);
    }
}

var numberOfArrays = function(differences, lower, upper) {
    let prefix = 0;
    let minVal = 0, maxVal = 0;
    
    for (let diff of differences) {
        prefix += diff;
        minVal = Math.min(minVal, prefix);
        maxVal = Math.max(maxVal, prefix);
    }
    
    let range = maxVal - minVal;
    let available = upper - lower;
    
    if (range > available) {
        return 0;
    }
    
    return available - range + 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 需要遍历一次 differences 数组计算前缀和
空间复杂度O(1) - 只使用常数额外空间存储变量