题目描述
难度分:1300
输入T(≤104)表示T组数据。所有数据的n之和≤3×105。
每组数据输入n(1≤n≤105)和长为n的数组a(−105≤a[i]≤105)。
从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 → 这个前缀和上一次出现的位置”。初始情况下mp[0]=0,在遍历i∈[1,n]的过程中维护前缀和sum=Σk∈[1,i]a[i]。如果前面出现过一次sum,即mp[sum]=j<i,那么子数组(j,i]的累加和就是0,马上分出来一个子数组。但j还需要满足j≥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;
}