問題描述

給定一個長度為 $n$ 的正整數陣列，計算總和為 $x$ 的子陣列數量

練習題

CSES - Subarray Sums I

這題保證正整數，所以加上某值之後，總和必定比原本大；減掉某值之後，總和必定比原本小。

可以用 Sliding Widnow 來解，若目前總和比 $x$ 小，就將右指標往右一格；若目前總和比 $x$ 大，就將左指標往右一格；如果目前總和就是我們要的，把答案加上去後，將左指標右移一格（或右指標右移一格）。

時間複雜度 $O(n)$

連結：https://cses.fi/problemset/task/1660/

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    ll x;
    cin >> n >> x;
    int arr[200005];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int left = 0;
    int right = -1;
    ll sum = 0;
    int ans = 0;
    while (right < n) {
        while (right < n && sum < x) {
            right++;
            sum += arr[right];
        }
        while (left <= right && sum > x) {
            sum -= arr[left];
            left++;
        }
        if (sum == x) {
            ans++;
            sum -= arr[left];
            left++;
        }
    }
    cout << ans;
}

CSES - Subarray Sums II

連結：https://cses.fi/problemset/task/1661/

與上題不一樣的是，這題不保證正整數，所以加上某值之後，總和未必比原本大；減掉某值之後，總和未必比原本小，因此無法使用 Sliding Window 維護，可以轉而用 前綴和 + Map。

設 $[0,j]$ 的總和為 prefix[j]，$[0,i]$ 的總和為 prefix[i]，且$[i+1,j]$ 的總和為 $x$

那麼此式成立： prefix[j] - prefix[i] = X

移項可得： prefix[j] - X = prefix[i]

因此我們只要將 prefixSum 加入 map 中，並找 prefixSum - X 的前綴和有幾個即可。

時間複雜度 $O(nlogn)$

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    ll x;
    cin >> n >> x;
    int arr[200005];
    for (int i = 0; i < n; i++) cin >> arr[i];
    map<ll, ll> prefixSum;
    prefixSum[0] = 1;
    ll cnt = 0;
    ll prefix = 0;
    for (int i = 0; i < n; i++) {
        prefix += arr[i];
        cnt += prefixSum[prefix - x];
        prefixSum[prefix]++;
    }
    cout << cnt;
}

CSES - Subarray Divisibility

這題是要找有多少個子陣列，其所有元素的總和可以被 n 整除。

可以沿用上一題的方法，前綴和 + Map，但查詢的東西不太一樣。

若 sum(i+1,j) = prefix[j] - prefix[i]

如果這個子陣列要被 n 整除，則： (prefix[j] - prefix[i]) mod n = 0

也就是：

prefix[j] mod n = prefix[i] mod n

這表示如果兩個前綴和模 $n$ 的結果相同，則它們中間的子陣列就符合條件

時間複雜度 O(nlogn)

負數取模

C++ 中 $-7$ % $3 = -1$

這會導致我們無法安全地把 % 結果當作 map 的 key（因為 key 應該在 0 ~ n-1 之間）

可以使用這個技巧來正規化負數：

((prefix + arr[i]) % n + n) % n

這樣無論 prefix 是正或負，都會落在 0 ~ n-1 之間

((2 - 3) % 4 + 4) % 4 = 3 不是 -1

換種想法：

目標為 5 餘數為 4，代表還要 +1 才能達到目標(5)

目標為 5 餘數為 -1，代表還要 +1 才能達到目標(0)，所以他要被當成餘數為 4

若以為 -1 換成餘數為 1 的話，代表要 +4 才可以達到目標，但 -1 + 4 為 3 並不符合

完整程式碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n;
    cin >> n;
    int arr[200005];
    for (int i = 0; i < n; i++) cin >> arr[i];
    map<ll, ll> prefixSum;
    prefixSum[0] = 1;
    ll cnt = 0;
    ll prefix = 0;
    for (int i = 0; i < n; i++) {
        prefix = ((prefix + arr[i]) % n + n) % n;
        cnt += prefixSum[prefix];
        prefixSum[prefix]++;
    }
    cout << cnt;
}