Assuming there is an array x[] with N elements, each greater than zero; we define x[0] + x[1] + … + x[i] as the prefix sum, and x[j] + x[j+1] + … + x[n-1] as the suffix sum. Please write a program to determine how many pairs of prefix sums and suffix sums are equal in x[].
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| Each test data file contains only one set of data, consisting of two lines. The first line contains an integer N (1 ≤ N ≤ 100000) representing the number of digits in the sequence. The second line contains N positive integers (A₁, A₂, ..., Aₙ), and the sum of all the integers is less than 2147483647, separated by spaces. | The number of pairs with equal prefix and suffix sums. |
| 7 3 6 2 1 4 5 2 | 3 |
Thought Process
Calculate the prefix sum from the left and record all prefix sums into a Map.
Next, calculate the suffix sum. If a prefix sum is recorded in the Map, it indicates a duplicate, so increase the answer by 1.
Sample Code－ZeroJudge D563: Equivalency
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int>num;
map<int, int>MAP;
int sum = 0;
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num.push_back(tmp);
sum += tmp;
MAP[sum]++;
}
sum = 0;
int ans = 0;
for (int i = N-1; i>=0; i--) {
sum += num[i];
if (MAP[sum] > 0) ans++;
}
cout << ans << "\n";
}
//ZeroJudge D563
//Dr. SeanXD