LeetCode 2145. 统计隐藏数组数目（前缀和）

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

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        // 求前缀和
        vector<long 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] = (i>0 ? presum[i-1] : 0)+differences[i];
            maxprevsum = max(maxprevsum, presum[i]);
            minprevsum = min(minprevsum, presum[i]);
        } 
        // a0 是第一个数，那么数组内最大的数是 a0+maxprevsum, 最小的数字是 a0+minprevsum
        // a0+maxprevsum <= upper  and a0+minprevsum >= lower
        //         lower-minprevsum <= a0 <= upper-maxprevsum
        //    加上题目的条件   lower <= a0 <= upper
        long long ans = min(1LL*upper, upper-maxprevsum) - max(1LL*lower, lower-minprevsum)+1;
        return ans >= 0 ? ans : 0;
    }
};