Table of contents
題目介紹
題目：計算奇數和子陣列的數量
描述： 給定一個整數陣列 arr，要求計算出所有可能的子陣列（連續的元素序列）中，總和為奇數的子陣列個數。
由於結果可能非常大，需要將答案對 10^9 + 7 取模。
例如：
- 輸入：arr = [1,3,5]
- 這個陣列的所有可能子陣列有：
- [1] -> 和為 1 (奇數)
- [3] -> 和為 3 (奇數)
- [5] -> 和為 5 (奇數)
- [1,3] -> 和為 4 (偶數)
- [3,5] -> 和為 8 (偶數)
- [1,3,5] -> 和為 9 (奇數)
- 總共有 4 個子陣列的和為奇數
- 輸出：4
解題思路
-
前綴和的概念
- 前綴和是指從數組開頭到當前位置的所有數字之和
- 例如數組 [1,3,5]，其前綴和為：
- index -1: 0
- index 0: 1
- index 1: 1+3 = 4
- index 2: 1+3+5 = 9
-
為什麼使用前綴和？
- 任何子陣列的和都可以用兩個前綴和相減得到
- 例如要求 index 1 到 2 的子陣列和：
- 可以用 前綴和[2] - 前綴和[0] = 9 - 1 = 8
- 這樣可以快速計算任何子陣列的和
-
奇偶性質的運用
- 當我們要找奇數和的子陣列時，可以利用奇偶性質：
- 偶數 - 偶數 = 偶數
- 奇數 - 奇數 = 偶數
- 奇數 - 偶數 = 奇數
- 偶數 - 奇數 = 奇數
- 當我們要找奇數和的子陣列時，可以利用奇偶性質：
-
解題策略
-
我們要找的是”和為奇數”的子陣列，可以用以下方式來思考：
-
第一步：追蹤前綴和的奇偶性
- 從左到右遍歷數組時，持續計算前綴和
- 只需記錄前綴和的奇偶性（因為我們只關心最後的和是奇數還是偶數）
- 使用兩個計數器：
- odd：記錄奇數前綴和出現的次數
- even：記錄偶數前綴和出現的次數（初始為1，因為空前綴和為0是偶數）
-
第二步：如何找到奇數和的子陣列？
- 假設我們現在在位置 i，前綴和為 sum_i
- 如果要使子陣列和為奇數，我們需要找到一個之前的位置 j，使得：
- sum_i - sum_j = 奇數
- 這代表：
- 如果 sum_i 是奇數，我們需要減去一個偶數前綴和
- 如果 sum_i 是偶數，我們需要減去一個奇數前綴和
-
舉例說明：
- 數組是 [1,3,5]
- 前綴和序列是：0,1,4,9
- 在計算過程中：
- 位置0（和為1）：奇數，可以和初始的0（偶數）相減，得到子陣列[1]和為1（奇數）
- 位置1（和為4）：偶數，可以和位置0的1（奇數）相減，得到子陣列[3]和為3（奇數）
- 位置2（和為9）：奇數，可以和：
- 初始的0（偶數）相減，得到子陣列[1,3,5]和為9（奇數）
- 位置1的4（偶數）相減，得到子陣列[5]和為5（奇數）
-
最終統計：
- 在這個例子中：
- odd（奇數前綴和）= 2（分別是1和9）
- even（偶數前綴和）= 2（分別是初始的0和4）
- 所以總共有 odd × even = 2 × 2 = 4 個奇數和子陣列
- 在這個例子中：
-
-
複雜度分析
-
時間複雜度：O(n)
- 我們只需要遍歷數組一次，對每個元素進行簡單的計算
- 每次操作（更新前綴和奇偶性、增加計數器）都是 O(1) 常數時間
- 因此總時間複雜度就是 O(n)，其中 n 是數組長度
-
空間複雜度：O(1)
- 我們只使用了有限的變數（even、odd、s）來記錄狀態
- 這些變數的數量不會隨著輸入數據的大小增加
- 無論輸入數組有多大，所需的額外空間都是固定的
- 因此空間複雜度為 O(1) 常數空間
-
效率對比
- 暴力解法需要計算所有可能的子數組和，時間複雜度為 O(n²)
- 我們的解法利用數學性質，一次遍歷就能解決，顯著提升了效率
- 在處理大規模數據時，這種 O(n) 的解法比暴力方法快得多
-
代碼實現
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
mod = 10**9 + 7
even, odd = 1, 0 # even count initialized for prefix sum parity 0
s = 0
for num in arr:
s ^= (num & 1) # update parity using XOR
if s:
odd += 1
else:
even += 1
return (odd * even) % mod常見問題與解答
-
Q: 為什麼初始化 even = 1？ A: 因為空前綴和（sum = 0）也算一個偶數前綴和，這代表從數組開頭開始的子陣列
-
Q: 為什麼使用位運算？ A: 使用位運算（XOR和AND）可以更有效率地計算奇偶性。特別是
num & 1用來取得數字的最低位元（判斷奇偶），而 XOR 運算則用於翻轉奇偶性。
總結
今天我們看的這題「計算奇數和子陣列的數量」真的很有趣！乍看之下，你可能會想著：「嗯，我就把所有子陣列都算出來，然後檢查哪些和是奇數就好了」—但這樣的暴力解法會讓你的程式跑很久（時間複雜度 O(n²)）。
而我們學到的這個解法可是聰明多了！用前綴和加上奇偶性的特性，我們只要：
- 走一遍陣列，記錄前綴和的奇偶性就好
- 不用記住每個前綴和是多少，只要知道「有幾個是奇數、有幾個是偶數」
- 用簡單的乘法公式 odd × even 就能算出所有奇數和子陣列的數量
這種解法不僅快（只要 O(n) 時間），而且超級省空間（只用了幾個變數）。
這個技巧真的很實用，不只適用於這題，還可以應用在很多類似的「子陣列和」問題上。下次如果你遇到類似的題目，可以試著想想：我是不是可以用前綴和？是不是只需要關注某些特定的性質，而不是具體的數值呢？
記住這個思路，會讓你在解決子陣列相關的問題時更加得心應手喔！