解題說明
題目描述
給定整數陣列 nums 和整數 k，回傳元素總和可被 k 整除的（非空）子陣列的數目。
範例：nums = [4, 5, 0, -2, -3, 1], k = 5
- [5] → 5 ÷ 5 = 1 ✓
- [5, 0] → 5 ÷ 5 = 1 ✓
- [0] → 0 ÷ 5 = 0 ✓
- [-2, -3] → -5 ÷ 5 = -1 ✓
- [5, 0, -2, -3] → 0 ÷ 5 = 0 ✓
- [4, 5, 0, -2, -3, 1] → 5 ÷ 5 = 1 ✓
- [0, -2, -3, 1] → -4... → 4, 5, 0, -2, -3, 1 共 7 個，答案為 7
解題思路
核心數學：前綴和 + 同餘定理 + 計數
與 LC 523 的判斷存在性不同，本題需要計算個數。
關鍵觀察：設 prefix[j] - prefix[i] 是 k 的倍數，則 prefix[j] % k == prefix[i] % k（同餘）。
因此，問題轉化為：計算所有前綴和中，餘數相同的兩兩配對數（C(count, 2) = count * (count-1) / 2）。
演算法
- 維護
count[r]表示前綴和餘數為r的個數（初始count[0] = 1，代表前綴和為 0 的空前綴）。 - 遍歷陣列，累積前綴和
sum，計算rem = sum % k。 - 當前
rem對應的配對數為count[rem]（之前出現過rem的次數），加入答案。 count[rem]++。
C++ 負數取模陷阱：C++ 中 (-2) % 5 = -2（向零取整），但數學意義上餘數應為正（-2 mod 5 = 3）。正確寫法：rem = ((sum % k) + k) % k，確保餘數始終非負。
為什麼不是 C(count, 2) 而是累加 count？
因為我們是線上計算——遍歷到 j 時，count[rem] 恰好是 j 之前出現過相同餘數的次數，每個都與 j 配對形成一個合法子陣列，所以直接加 count[rem] 即可（等效於最終計算 C(count, 2) 的累計版本）。
C++ 解法
複雜度分析
時間複雜度
O(n)，其中 n 為陣列長度。只需一次線性遍歷，每次 HashMap（或陣列）操作均為 O(1)。
若使用固定大小陣列（Solution2），常數因子更小，因為避免了 HashMap 的雜湊計算開銷。
空間複雜度
- HashMap 版本：O(min(n, k))，最多儲存 k 個不同餘數（0 到 k-1）。
- 陣列版本：O(k)，固定大小 k 的計數陣列，空間確定且快取友好。
虛擬碼
1. Initialize count array/map with count[0] = 1 2. sum = 0, result = 0 3. For each x in nums: a. sum += x b. rem = ((sum % k) + k) % k // ensure non-negative c. result += count[rem] // count previous prefixes with same remainder d. count[rem] += 1 4. Return result
其他解法
替代方案
方案一：暴力枚舉
雙重迴圈枚舉所有子陣列，用前綴和 O(1) 計算子陣列和，再判斷是否整除 k。
- 優點：邏輯直觀。
- 缺點：時間 O(n²)，n=30000 時約 9×10^8 操作，無法通過。
方案二：計算所有前綴和，然後批量配對
先計算所有 n+1 個前綴和（含空前綴），對每個前綴和取模，最後統計各餘數的出現次數，用 C(count[r], 2) 計算配對數。
- 優點：邏輯清晰，與線上計算等價；更容易理解「相同餘數的配對」這一核心思想。
- 缺點：需要額外 O(n) 空間儲存前綴和；分兩步實作，不如線上版本簡潔。兩者時間複雜度相同（O(n)）。
方案三：桶排序 + 配對計算
同方案二，但在第二步用桶（大小為 k 的陣列）替代 HashMap，最後遍歷所有桶計算 C(count[r], 2) 並求和。
- 優點：避免 HashMap 開銷，常數因子最小；空間 O(k)，適合 k 較小的情況。
- 缺點：若 k 很大（如 10^5），桶的空間需求也大；Solution2 已採用此方案。
延伸思考
延伸問題
-
子陣列和恰好為 k（不是倍數）：這是 LC 560（Subarray Sum Equals K），同樣用前綴和 + HashMap，但不需要取模，直接用
count[sum - k]計算，是本題的簡化版本。 -
判斷是否存在（非計數）：若只需判斷是否存在長度 ≥ 2 的子陣列和為 k 的倍數（LC 523），HashMap 中只記錄最早出現的索引即可，無需計數；當找到相同餘數且距離 ≥ 2 時即回傳 true。
-
負數取模的通用處理：在 Python 中
-2 % 5 = 3（正餘數），而在 C++/Java 中-2 % 5 = -2（向零取整）。通用公式((x % k) + k) % k在任何語言中都能確保非負餘數，是處理「負數前綴和取模」問題的標準寫法，必須熟記。