好的！讓我們詳細解釋 LeetCode 1524. 和為奇數的子數組數目 這道題的思路和解法。

題目： https://leetcode.cn/problems/number-of-sub-arrays-with-odd-sum/description/

題目分析

問題描述：
給定一個整數數組 arr，返回其中和為奇數的子數組的數目。由于答案可能很大，結果需對 10^9 + 7 取余。

示例：
輸入：arr = [1, 3, 5]
輸出：4
解釋：

• 子數組 [1]、[3]、[5] 的和均為奇數。
• 子數組 [1, 3, 5] 的和為 1 + 3 + 5 = 9，也是奇數。

暴力解法（超時）

思路：
枚舉所有子數組，計算每個子數組的和并判斷奇偶性。

代碼：

class Solution {
public:int numOfSubarrays(vector<int>& arr) {const int MOD = 1e9 + 7;int count = 0;int n = arr.size();for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += arr[j];if (sum % 2 == 1) {count = (count + 1) % MOD;}}}return count;}
};

復雜度：

• 時間復雜度：O(n2)
• 空間復雜度：O(1)

優化解法：前綴和 + 奇偶計數

核心思路：

1. 前綴和的奇偶性：子數組 [i, j] 的和為 prefix[j+1] - prefix[i]，其中 prefix[k] 表示前 k 個元素的和。
2. 奇偶性規律：若 prefix[j+1] 和 prefix[i] 的奇偶性不同，則子數組和為奇數。
3. 哈希表統計：動態維護前綴和為奇數和偶數的次數，遍歷數組時累加符合條件的子數組數目。

代碼：

class Solution {
public:int numOfSubarrays(vector<int>& arr) {const int MOD = 1e9 + 7;int count = 0;int prefix = 0;      // 當前前綴和int odd = 0;         // 前綴和為奇數的次數int even = 1;        // 前綴和為偶數的次數（初始包含前綴和為0的情況）for (int num : arr) {prefix += num;if (prefix % 2 == 0) {// 當前前綴和為偶數，加上之前前綴和為奇數的次數count = (count + odd) % MOD;even++;} else {// 當前前綴和為奇數，加上之前前綴和為偶數的次數count = (count + even) % MOD;odd++;}}return count;}
};

復雜度：

• 時間復雜度：O(n)
• 空間復雜度：O(1)

詳細解釋

1. 前綴和的奇偶性：
   對于子數組 [i, j]，其和為 prefix[j+1] - prefix[i]。

   • 若 prefix[j+1] 為偶數，prefix[i] 為奇數，則和為奇數。
   • 若 prefix[j+1] 為奇數，prefix[i] 為偶數，則和為奇數。

2. 動態維護奇偶次數：

   • odd：記錄遍歷到當前位置時，前綴和為奇數的次數。
   • even：記錄遍歷到當前位置時，前綴和為偶數的次數。
   • 初始值：even = 1，因為空數組的前綴和為 0（偶數）。

3. 累加結果：

   • 若當前前綴和為偶數，則它可以與之前所有奇數前綴和形成有效子數組，累加 odd。
   • 若當前前綴和為奇數，則它可以與之前所有偶數前綴和形成有效子數組，累加 even。

示例驗證

輸入：arr = [1, 3, 5]
步驟如下：

1. 初始狀態：prefix = 0，odd = 0，even = 1，count = 0。
2. 處理 1：prefix = 1（奇數），count += even = 1，odd = 1，even = 1。
3. 處理 3：prefix = 4（偶數），count += odd = 1 + 1 = 2，odd = 1，even = 2。
4. 處理 5：prefix = 9（奇數），count += even = 2 + 2 = 4，odd = 2，even = 2。

最終結果：4，與預期一致。

總結

通過前綴和的奇偶性分析和動態計數，我們將時間復雜度從 O(n2) 優化到 O(n)，空間復雜度為 O(1)。這種方法適用于所有類似的“子數組和滿足某種奇偶性條件”的問題，核心在于利用前綴和的奇偶性快速查找配對。