Leetcode 1524. 和為奇數的子陣列數量

這是 Leetcode 2025 年 2 月 25 日的每日一題。

題目描述
#

給定一個整數陣列 arr，請回傳總和為奇數的子陣列數量。

由於答案可能很大，請對 $10^9 + 7$ 取模後回傳。

解題思路 - 暴力 DP
#

定義 dp[i][j] 表示從索引 $i$ 到 $j$ 的子陣列總和的奇偶性。若總和為奇數，則 dp[i][j] = true，否則為 false。
統計 dp 中值為 true 的項數，並對 $10^9+7$ 取模後回傳。
規則為：
- 若 arr[j] 為奇數且 dp[i][j-1] 為偶數，則 dp[i][j] 為奇數；
- 或者 arr[j] 為偶數且 dp[i][j-1] 為奇數，也會導致 dp[i][j] 為奇數。

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        int result = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        for(int i = 0; i < n; i++){
            if (arr[i] % 2 == 1){
                dp[i][i] = true;
                result = (result + 1) % MOD;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if ((dp[i][j-1] == true && (arr[j] % 2 == 0)) || (dp[i][j-1] == false && (arr[j] % 2 == 1))){
                    dp[i][j] = true;
                    result = (result + 1) % MOD;
                }
            }
        }
        return result;
    }
};

時間複雜度：$O(n^2)$，本題會 TLE
空間複雜度：$O(n^2)$

解題思路 - 動態規劃（DP）
#

定義 dpEven[i] 為以索引 $i$ 結尾且總和為偶數的子陣列數量； dpOdd[i] 則為總和為奇數的子陣列數量。
如果 arr[i] 是奇數，則：
- 可以將 arr[i] 加在一個偶數總和的子陣列後形成奇數總和；
- 或者 arr[i] 自己成為一個長度為 1 的奇數總和子陣列。
所以：
- dpOdd[i] = dpEven[i-1] + 1
- dpEven[i] = dpOdd[i-1]
若 arr[i] 是偶數，則不改變原有子陣列的奇偶性。
最後統計所有 dpOdd[i] 的總和即為答案。

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> dpEven(n, 0);
        vector<int> dpOdd(n, 0);
        dpEven[0] = (arr[0] % 2 == 1) ? 0: 1;
        dpOdd[0] = (arr[0] % 2 == 1) ? 1: 0;
        for(int i = 1; i < n; i++){
            if(arr[i] % 2 == 1){
                dpOdd[i] = (dpEven[i-1] + 1) % MOD;
                dpEven[i] = (dpOdd[i-1]) % MOD;
            }
            else{
                dpOdd[i] = (dpOdd[i-1]) % MOD;
                dpEven[i] = (dpEven[i-1] + 1) % MOD;
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            result = (result + dpOdd[i]) % MOD;
        }
        return result;
    }
};

時間複雜度：$O(n)$
空間複雜度：$O(n)$

解題思路 - 前綴和
#

從 $i$ 到 $j$ 的子陣列總和可以寫成：
$$ \text{sum}(i,j)=\text{prefixSum}(j)−\text{prefixSum}(i−1) $$
若總和為奇數，表示 prefixSum(j) 和 prefixSum(i-1) 的奇偶性不同。
我們可以維護兩個變數：
- oddSum：目前為止 prefix sum 為奇數的次數
- evenSum：目前為止 prefix sum 為偶數的次數（初始為 1，因為 0 是偶數）
每次 prefix sum 更新後：
- 若為奇數，則能與所有之前的偶數 prefix 組合成奇數子陣列
- 若為偶數，則能與之前的奇數 prefix 組成奇數子陣列

Code
#

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        int prefixSum = 0;
        int oddSum = 0; // 目前為止奇數前綴和個數
        int evenSum = 1; // 初始為 1，因為 0 是偶數
        int result = 0;
        for(int num : arr){
            prefixSum += num;
            if (prefixSum % 2 == 1){
                result += evenSum;
                oddSum++;
            }
            else{
                result += oddSum;
                evenSum++;
            }
            result %= MOD;
        }
        return result;
    }
};