題意#
題目給定一個長度為 \( n \) 的整數陣列，以及目標總和 \( x \)。
需要找出總和剛好為 \( x \) 的「連續子陣列」數量。
與前一題不同，本題的陣列元素可能包含零與負數。
思路#
因為陣列包含負數，區間長度與總和的「單調性」被打破，無法使用雙指標（Sliding Window）求解。
針對此類可能包含負數的區間和問題，可利用「前綴和（Prefix Sum）」結合「Hash Map」處理。
子陣列 [L, R] 的總和可表示為 prefix[R] - prefix[L-1]。
題意要求總和為 \( x \)，即 prefix[R] - prefix[L-1] == x。
經移項後得到 prefix[L-1] == prefix[R] - x。
這意味著：當計算至位置 R 得到前綴和 prefix[R] 時，只需查詢過去的前綴和紀錄中，「數值為 prefix[R] - x 的前綴和出現過幾次」。
出現的次數即代表以目前位置 R 為右端點，且總和為 \( x \) 的子陣列數量。
實作上，在遍歷陣列計算前綴和的同時，使用 Hash Map 查詢 prefix[R] - x 的出現次數並累加至答案。
隨後，將當下的 prefix[R] 登記至 Map 中供後續查詢。
需特別注意，初始化時應加入 mp[0] = 1，代表前綴和為 0 的初始狀態（考慮從陣列開頭即符合條件的子陣列）。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, x; cin >> n >> x;
vector<int> v(n);
for (auto &i : v) cin >> i;
int ans = 0;
// mp 用來記錄「某個前綴和數值，在歷史中出現過幾次」
map<int, int> mp;
// 初始化，記錄「前綴和為 0 的情況出現過 1 次」
// 用以處理從陣列起點累積到當下恰好等於 x 的情況
mp[0] = 1;
// prefix 陣列用來存放算好的前綴和
vector<int> prefix(n+1);
for (int i = 1; i <= n; i++) prefix[i] = v[i-1]+prefix[i-1];
// 遍歷所有計算好的前綴和
for (int i = 1; i <= n; i++) {
// 去 Map 查詢能與當前 prefix[i] 搭配湊出 x 的舊前綴和出現次數
ans += mp[prefix[i]-x];
// 將當前的 prefix[i] 登記進入 Map 供未來查詢
mp[prefix[i]]++;
}
// 輸出符合條件的子陣列總數
cout << ans << '\n';
}
