d563 - 等值首尾和
題目描述
題目要求計算給定陣列中，前段和等於後段和的子陣列數量。前段和定義為從陣列開頭到某個索引的元素和，後段和定義為從某個索引到陣列結尾的元素和。
解題思路
本題的核心思想是利用前綴和和後綴和的特性。首先計算陣列的前綴和 sump 和後綴和 sumb。然後，使用一個哈希表 n (map) 儲存所有可能的前綴和值。最後，遍歷後綴和 sumb，如果 sumb[i] 在哈希表中存在，則表示存在一個前綴和等於該後綴和，計數器 ans 增加。
複雜度分析
- 時間複雜度: O(n)，其中 n 是陣列的長度。計算前綴和和後綴和需要 O(n) 的時間，遍歷後綴和並查找哈希表需要 O(n) 的時間。
- 空間複雜度: O(n)，因為哈希表
n最多可能儲存 n 個不同的前綴和值。
程式碼
#include <iostream>
#include <map>
using namespace std;
int main(){
int a;
map <int,int> n;
while(cin >> a){
int b[a],sump[a]={0},sumb[a]={0},ans=0;
for(int i=0;i<a;i++){
cin >> b[i];
sump[i]=b[i];
sumb[i]=b[i];
}
for(int i=1;i<a;i++)
sump[i]+=sump[i-1];
for(int i=a-2;i>=0;i--)
sumb[i]+=sumb[i+1];
for(int i=0;i<a;i++)
n[sump[i]]=0;
for(int i=a-1;i>=0;i--){
if(n.find(sumb[i])!=n.end())
ans++;
}
cout << ans << endl;
n.clear();
}
}