題目資訊

題目編號: 1524
題目連結: Number of Sub-arrays With Odd Sum
主題: Array, Math, Dynamic Programming, Prefix Sum

題目敘述

給定一個整數數組 arr，返回子陣列中具有奇數和的數目。

由於答案可能非常大，返回它對 $10^9 + 7$ 的取模。

範例 1:

輸入: arr = [1,3,5]
輸出: 4
解釋: 所有的子陣列是 [[1],[1,3],[1,3,5],[3],[3,5],[5]]
所有子陣列和是 [1,4,9,3,8,5]。
奇數和是 [1,9,3,5] ，所以答案是 4。

範例 2:

輸入: arr = [2,4,6]
輸出: 0
解釋: 所有的子陣列是 [[2],[2,4],[2,4,6],[4],[4,6],[6]]
所有子陣列和是 [2,6,12,4,10,6]。
所有子陣列和都是偶數和，答案是 0。

範例 3:

輸入: arr = [1,2,3,4,5,6,7]
輸出: 16

約束條件:

$1 \leq arr.length \leq 10^5$
$1 \leq arr[i] \leq 100$

直覺

此問題要求從給定的整數數組中計算具有奇數和的子數組的數量。子數組定義為數組中的連續部分。主要的挑戰在於如何有效地確定具有奇數和的子數組的數量，因為暴力方法由於限制條件的關係並不可行。此處的直覺是利用前綴和的屬性，使我們能夠使用先前計算的和來計算任何子數組的和。關鍵觀察在於子數組的和可以根據前綴和表示。具體而言，若索引 $i$ 到 $j$ 之間的元素和為奇數，只有當他們各自的前綴和之差為奇數時成立。

解法

該方法首先初始化計數器來跟蹤奇數和偶數的前綴和的數量。我們用 oddCount 表示具有奇數和的前綴子數組的數量，用 evenCount 表示具有偶數和的數量。最初，有一個空前綴具有偶數和（因此 evenCount = 1）。

演算法步驟如下：

遍歷數組 arr 中的每一個元素。
我們維護一個布林變量 isPrefixOdd 以表示當前的前綴和是否為奇數。它通過當前元素的奇偶性使用 XOR 進行更新。
如果 isPrefixOdd 為 true，這表示當前累積的前綴和為奇數：
- 將先前的偶數和的計數（evenCount）加入答案中，因為將新的奇數前綴與舊的偶數前綴配對會得到奇數子數組和。
- 增加 oddCount，因為我們遇到了一個新的奇數前綴和。
如果 isPrefixOdd 為 false，則當前的前綴和為偶數：
- 將先前的奇數和的計數（oddCount）加入答案中。將新的偶數前綴與舊的奇數前綴配對會得到奇數子數組和。
- 增加 evenCount，因為我們遇到了一個新的偶數前綴和。
由於結果可能會很大，請確保它不超過 $10^9 + 7$，通過在每一步取模來保證。
返回存儲在 ans 中的具有奇數和的子數組的總數。

此方法確保我們能夠有效地計算具有奇數和的子數組數量，而無需顯式計算每一個可能的子數組和，從而在約束條件內處理該問題。

程式碼

C++

#define MAX 1000000007

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int len = arr.size();
        int ans = 0;          // 用來儲存總共擁有奇數和的子陣列數量
        int oddCount = 0;     // 前綴子陣列和為奇數的計數
        int evenCount = 1;    // 前綴子陣列和為偶數的計數；初始設定為1表示初始前綴
        bool isPrefixOdd = false;  // 布林值用來追蹤當前的前綴和是否為奇數

        // 遍歷陣列中的每個元素
        for (int num : arr) {
            // 根據當前元素更新前綴奇數狀態
            isPrefixOdd ^= (num & 1);
            
            if (isPrefixOdd) {
                ans += evenCount;  // 如果當前前綴和為奇數，將偶數前綴計數加到答案中
                oddCount++;        // 奇數前綴子陣列的計數加一
            } else {
                ans += oddCount;   // 如果當前前綴和為偶數，將奇數前綴計數加到答案中
                evenCount++;       // 偶數前綴子陣列的計數加一
            }
            
            // 使用模數操作確保答案在限制範圍內
            if (ans >= MAX) {
                ans -= MAX;
            }
        }
        
        return ans;
    }
};

Python

class Solution:
    def numOfSubarrays(self, arr):
        MAX = 1000000007
        len_arr = len(arr)
        ans = 0          # 用於儲存總共有多少子陣列的和是奇數
        oddCount = 0     # 前綴子陣列中和為奇數的計數
        evenCount = 1    # 前綴子陣列中和為偶數的計數；初始值為1是因為初始前綴
        isPrefixOdd = False  # 布林值用於追蹤當前前綴和是否為奇數

        # 遍歷數組中的每個元素
        for num in arr:
            # 根據當前元素更新前綴奇數狀態
            isPrefixOdd ^= (num & 1)
            
            if isPrefixOdd:
                ans += evenCount  # 如果當前前綴和是奇數，將偶數前綴計數加到答案中
                oddCount += 1     # 增加奇數前綴子陣列的計數
            else:
                ans += oddCount   # 如果當前前綴和是偶數，將奇數前綴計數加到答案中
                evenCount += 1    # 增加偶數前綴子陣列的計數
            
            # 確保答案在限制範圍內通過取模運算
            if ans >= MAX:
                ans -= MAX
        
        return ans

複雜度分析

時間複雜度: $O(n)$
該演算法對陣列 arr 進行一次遍歷，對每個元素執行常數時間的操作。遍歷這個陣列所需的時間是與陣列大小 $n$ 成線性關係的。因此，時間複雜度為 $O(n)$。
空間複雜度: $O(1)$
該演算法使用固定數量的額外空間，與輸入陣列的大小無關。它維護了幾個整數變量（ans、oddCount、evenCount）和一個布林值（isPrefixOdd）。由於這些空間不隨著輸入大小增長，故空間複雜度為 $O(1)$。

CS Note
En

Leetcode 1524. Number of Sub-arrays With Odd Sum

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析