5972. 统计隐藏数组数目

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 117 阅读 / 876 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

给你一个下标从 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 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-the-hidden-sequences
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

计算两个区间长度差

代码:

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long range = upper - lower;
        long MIN=0,MAX=0,num=0;
        for(int i=0;i<differences.size();i++){
            num+=differences[i];
            MAX=max(MAX,num);
            MIN=min(MIN,num);
        }
        return (range-(MAX-MIN)+1)>0?(range-(MAX-MIN)+1):0;
    }
};
0

评论区