日期:2026年11月15日
LeetCode 題目連結:1524. Number of Sub-arrays With Odd Sum
解題想法
中等難度題。題目給一個整數陣列 $arr$,要找出 $arr$ 之中有幾個子陣列和為奇數,由於答案可能很大,要對 $10^9 + 7$ 取餘數。這題考數學,用兩個變數 $even, odd$ 分別記錄目前的加總為奇數、偶數的數量,假設 $arr[i] = a$,如果 $a$ 是奇數,則在 $a$ 之前加總為偶數的部分會變成奇數,加總為奇數的部分會變成偶數;如果 $a$ 是偶數,則在 $a$ 之前加總為奇數、偶數的部分性質不變。
Python 程式碼
Runtime: 85 ms, beats 47.26%. Memory: 24.37 MB, beats 93.04%.
class Solution:
def numOfSubarrays(self, arr: list[int]) -> int:
mod = 10**9 + 7 # 取餘數用的質數
even = 1 # 加總為偶數的數量,對於首項加總為 0
odd = 0 # 加總為奇數的數量
isum = 0 # 加總
ans = 0 # 答案
for a in arr:
isum += a
if isum % 2 == 1: # 加總為奇數
# 如果 a 之前的加總為偶數,加上 a 之後變成奇數,加入 ans
ans = (ans + even) % mod
odd += 1
else: # 加總為偶數
# 如果 a 之前的加總為奇數,加上 a 之後還是奇數,加入 ans
ans = (ans + odd) % mod
even += 1
return ans