[LeetCode] 每日一题 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 。

题目链接

https://leetcode.cn/problems/count-the-hidden-sequences

示例输入

示例 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^5

• -105 <= differences[i] <= 10^5

• -105 <= lower <= upper <= 10^5

解题思路

这题属于典型的前缀和建模问题，理解清楚 hidden 和 differences 之间的关系是关键。

根据题目描述，隐藏数组 hidden 满足 differences[i] = hidden[i+1] - hidden[i]。也就是说，只要确定了 hidden 的第一个元素，其余元素就完全确定了。

那这道题的思路就清晰了：

• 我们假设 hidden 的第一个元素是 0，那么可以直接通过累加 differences 来推导出一个“基础版”的 hidden。

• 这样推导出来的 hidden，可能有最大值和最小值。假设最大值是 max，最小值是 min。

• 如果 max - min 超过了 upper - lower，那无论怎么平移 hidden 整体，都无法把它控制在 [lower, upper] 区间内，直接返回 0。

• 否则，平移 hidden，使它的最小值落在 [lower, upper] 区间内即可。

• 有多少种平移方式呢？答案就是 upper - lower - (max - min) + 1 种！

这种思考方式就像是用前缀和构建出一个“形状”，然后通过整体平移来适配 [lower, upper] 区间，非常直观✨

代码实现

class Solution {
    public int numberOfArrays(int[] differences, int lower, int upper) {
        long x = 0, min = 0, max = 0;
        for (int d : differences) {
            x += d;
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        return (int)Math.max(upper - lower - (max - min) + 1, 0);
    }
}

复杂度分析

• 时间复杂度：O(n) 🚀
  只需要遍历一次 differences 数组，顺便记录最大值和最小值

• 空间复杂度：O(1) 🧠
  只使用了常数个变量，没有额外开辟空间

总结

这道题核心是前缀和建模 + 平移处理，一开始看似比较抽象，但只要理解了 hidden 和 differences 的关系，问题就非常简单了。遇到类似“相邻差值固定”的题目时，优先考虑前缀和思路，往往可以一击即中！💡

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。