牛牛满意的数组题解

在牛牛面前有n个数字构成的数组，牛牛特别喜欢数字，而且他对数字非常敏感。
牛牛心中满意的数组需要满足以下条件：
1.这个数组是原数组的其中一个子数组
2.如果这个数组的所有的子数组中所有的元素和不为0，那么他对这个数组是满意的
其中，子数组的定义为：删除一个数组前0个或多个元素或者删除一个数组后0个或多个元素，得到的数组就是原数组的子数组，例如对于数组[1,2,3]，那么它的子数组为[1],[1,2],[1,2,3],[2,3],[3],[2]。
给出一个数组，请找出这个数组中牛牛满意的子数组的数量最多是多少？

时间复杂度 空间复杂度
题目分析：我们知道，对于一个长度为n的数组来说，有 个子数组。题目中，n 高达 ，所以肯定不能暴力去枚举，但是因为子数组是连续的，加上题目将子数组之和作为判断条件，想到这里，我们不难想到可以维护一个前缀和 sum 方便后续操作。
解法：我们可以从左往右依次遍历，用一个map记录当前前缀和的值是否在之前出现过。如果出现过，那么之前的位置到当前的位置的这些子数组都是不能让牛牛满意的，根据这个方法可以统计出正确答案，代码如下：

/**
 * 返回一个数组中牛牛满意的子数组的数量最多是多少
 * @param n int整型 代表一共有多少数
 * @param a int整型vector 代表每个数的大小
 * @return long长整型
 */
long long solve(int n, vector<int> &a)
{
    // write code here
    map<long long, int> mp;
    long long sum = 0, ans = 0, maxL = 1;
    mp[0] = 1; //初始前缀和为0
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
        if (mp[sum] != 0)
            maxL = max(maxL, (long long)(mp[sum] + 1));
        ans += (i - maxL + 2);
        mp[sum] = (i + 2);
    }
    return ans;
}