# 2145. Count the Hidden Sequences
###### tags: `Leetcode` `Medium` `Prefix Sum`
Link: https://leetcode.com/problems/count-the-hidden-sequences/description/
## 思路
假设```differences```的第一个数字为0 然后求prefix sum 这样就知道整个seq array的变化幅度
用upper-lower-seq array的变化幅度就是答案
## Code
$O(N)$ $O(N)$

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        n = len(differences)
        seq = [0]*(n+1)
        for i in range(n):
            seq[i+1] = seq[i]+differences[i]
        minVal = min(seq)
        maxVal = max(seq)
        if maxVal-minVal>upper-lower: return 0
        else: return upper-lower-(maxVal-minVal)+1

空间优化
$O(N)$ $O(1)$

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        n = len(differences)
        for i in range(1,n):
            differences[i] += differences[i-1]
        minVal = min(differences+[0])
        maxVal = max(differences+[0])
        if maxVal-minVal>upper-lower: return 0
        else: return upper-lower-(maxVal-minVal)+1