假設有一個陣列 x[]，它有 N 個元素，每一個都大於零；我們說 x[0] + x[1] + … + x[i] 是個前段和 (Prefix Sum)，而 x[j] + x[j+1] + … + x[n-1] 則是個後段和 (Suffix Sum)。請寫一個程式，求出 x[] 中有多少組相同的前段和與後段和。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 每個測資檔只有一組測資，共兩行。 第一行整數 N (1 <= N <= 100000) 代表數列有幾個數字。 第二行有 N 個正整數 (A1, A2, …, AN)，並且全部總合小於 2147483647，以空格隔開 | 等值首尾和的數目 |
| 7 3 6 2 1 4 5 2 | 3 |
解題思路
計算左前綴合，並且將所有左前綴合記錄到一個 Map 中。
再來要計算右前綴合，如果有前綴合在 Map 中有紀錄，就代表有重複將答案 +1。
範例程式碼－ZeroJudge D563: 等值首尾和
#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