You are given a 0-indexed array of n
integers differences
, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1)
. More formally, call the hidden sequence hidden
, then we have that differences[i] = hidden[i + 1] - hidden[i]
.
You are further given two integers lower
and upper
that describe the inclusive range of values [lower, upper]
that the hidden sequence can contain.
- For example, given
differences = [1, -3, 4]
,lower = 1
,upper = 6
, the hidden sequence is a sequence of length4
whose elements are in between1
and6
(inclusive).[3, 4, 1, 5]
and[4, 5, 2, 6]
are possible hidden sequences.[5, 6, 3, 7]
is not possible since it contains an element greater than6
.[1, 2, 3, 4]
is not possible since the differences are not correct.
Return the number of possible hidden sequences there are. If there are no possible sequences, return 0
.
Example 1:
Input: differences = [1,-3,4], lower = 1, upper = 6 Output: 2 Explanation: The possible hidden sequences are: - [3, 4, 1, 5] - [4, 5, 2, 6] Thus, we return 2.
Example 2:
Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5 Output: 4 Explanation: The possible hidden sequences are: - [-3, 0, -4, 1, 2, 0] - [-2, 1, -3, 2, 3, 1] - [-1, 2, -2, 3, 4, 2] - [0, 3, -1, 4, 5, 3] Thus, we return 4.
Example 3:
Input: differences = [4,-7,2], lower = 3, upper = 6 Output: 0 Explanation: There are no possible hidden sequences. Thus, we return 0.
Constraints:
n == differences.length
1 <= n <= 105
-105 <= differences[i] <= 105
-105 <= lower <= upper <= 105
Solution: Math
Find the min and max of the cumulative sum of the differences.
Ans = max(0, upper – lower – (hi – lo) + 1)
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int numberOfArrays(vector<int>& differences, int lower, int upper) { long long s = 0; long long hi = 0; long long lo = 0; for (int d : differences) { s += d; hi = max(hi, s); lo = min(lo, s); } return max(0LL, upper - lower - (hi - lo) + 1); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment