未成年人思想道德建设网站,电子贺卡制作模板,关岭县建设局网站,开发工具怎么调出来文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始且长度为 n 的整数数组 differences #xff0c;它表示一个长度为 n 1 的 隐藏 数组 相邻 元素之间的 差值 。 更正式的表述为#xff1a;我们将隐藏数组记作 hidden #xff0c;那么 differences[i] hidden[i 1] -…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 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.length
1 n 10^5
-10^5 differences[i] 10^5
-10^5 lower upper 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-the-hidden-sequences 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
利用前缀和得到 hidden 数组内的最大最小的数字然后首项、最大、最小的数字都需要在闭区间内
class Solution {
public:int numberOfArrays(vectorint differences, int lower, int upper) {// 求前缀和vectorlong long presum(differences.size());long long n differences.size(), maxprevsum LONG_LONG_MIN, minprevsum LONG_LONG_MAX;for(int i 0; i n; i){presum[i] (i0 ? presum[i-1] : 0)differences[i];maxprevsum max(maxprevsum, presum[i]);minprevsum min(minprevsum, presum[i]);} // a0 是第一个数那么数组内最大的数是 a0maxprevsum, 最小的数字是 a0minprevsum// a0maxprevsum upper and a0minprevsum lower// lower-minprevsum a0 upper-maxprevsum// 加上题目的条件 lower a0 upperlong long ans min(1LL*upper, upper-maxprevsum) - max(1LL*lower, lower-minprevsum)1;return ans 0 ? ans : 0;}
};204 ms 113 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
