题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(-10^5 \leq a[i] \leq 10^5)$。

从$a$中选出若干非空连续子数组，要求任意两个子数组都不相交，且每个子数组的元素和都是$0$。

输出你最多可以选多少个子数组。

输入样例

3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1

输出样例

1
2
3

算法

贪心

比较容易想到“两数之和”的解法，准备一个哈希映射表$mp$，它表示“前缀和$sum$ $\rightarrow$ 这个前缀和上一次出现的位置”。初始情况下$mp[0]=0$，在遍历$i \in [1,n]$的过程中维护前缀和$sum=\Sigma_{k \in [1,i]}a[i]$。如果前面出现过一次$sum$，即$mp[sum]=j \lt i$，那么子数组$(j,i]$的累加和就是$0$，马上分出来一个子数组。但$j$还需要满足$j \geq pre$，$pre$是上一个分出来的$0$累加和子数组结尾。分出$(j,i]$这个子数组后，更新$pre=i$。

复杂度分析

时间复杂度

遍历了一遍数组就得到了答案，所以时间复杂度为$O(n)$。

空间复杂度

算法过程中开辟了一个哈希表用来存某个前缀和的出现位置，在最差情况下每个位置的前缀和都不相同，需要存$O(n)$个前缀和。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 300010;
int t, n, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve() {
    unordered_map<LL, int, custom_hash> mp;
    mp[0] = 0;
    LL sum = 0;
    int ans = 0, pre = 0;
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        if(mp.count(sum) && mp[sum] >= pre) {
            pre = i;
            ans++;
        }
        mp[sum] = i;
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}