Count Stable Segments in an Array with Prefix Sums
unknown
c_cpp
a year ago
521 B
18
Indexable
using ll = long long;
int countStableSegments(vector<int> arr) {
int n = arr.size();
if(n <= 2)
return 0;
unordered_map<int, unordered_map<ll, ll>>dp;//[cur][psum]
dp[arr[0]][arr[0]] = 1;
ll cur_sum = arr[0], ans = 0;
for(int i = 1; i < n; i++){
int x = arr[i];
if(dp.count(arr[i])){
if(dp[x].count(cur_sum-x))
ans += dp[x][cur_sum-x];
}
cur_sum += arr[i];
dp[arr[i]][cur_sum]++;
}
return ans;
}Editor is loading...
Leave a Comment