解題說明
題目描述
給定一個整數陣列 nums 和整數 k，判斷陣列中是否存在長度至少為 2 的連續子陣列，使得其總和為 k 的倍數（即總和 mod k == 0）。
範例：nums = [23, 2, 4, 6, 7], k = 6
- 子陣列 [2, 4] 的和為 6，是 6 的倍數，且長度 ≥ 2 → 回傳 true
解題思路
核心數學：前綴和 + 同餘定理
關鍵觀察：若子陣列 nums[i+1..j] 的和是 k 的倍數，設前綴和 prefix[i] 和 prefix[j]，則：
(prefix[j] - prefix[i]) % k == 0
⟺ prefix[j] % k == prefix[i] % k
換言之，兩個前綴和對 k 的餘數相同，則其間的子陣列和為 k 的倍數。
演算法
- 用 HashMap 儲存每個餘數第一次出現的索引。
- 遍歷陣列，維護當前前綴和
sum，計算rem = sum % k。 - 若
rem已在 HashMap 中，且當前索引與 HashMap 中的索引相差 ≥ 2（確保子陣列長度 ≥ 2），則找到答案。 - 否則，若
rem不在 HashMap 中，才將其加入（保留最早出現的索引，以最大化子陣列長度）。
初始化：HashMap 中預先放入 {0: -1}，處理從索引 0 開始的子陣列（前綴和本身已是 k 的倍數的情況）。
邊界條件
k = 0的特殊處理：若 k = 0，不能做模運算，改為直接檢查前綴和差值是否為 0。- 長度至少 2：條件為
i - map[rem] >= 2（當前索引 i 與最早索引至少差 2）。
C++ 解法
複雜度分析
時間複雜度
O(n)，其中 n 為陣列長度。只需遍歷一次陣列，每次雜湊表的插入與查詢均為 O(1) 平均時間。
空間複雜度
O(min(n, k))，HashMap 最多儲存 k 個不同的餘數（0 到 k-1）。若 k 很大，則最多儲存 n 個不同的餘數。整體上不超過 O(n)。
虛擬碼
1. Initialize HashMap firstSeen = {0: -1}
2. Initialize sum = 0
3. For i from 0 to n-1:
a. sum += nums[i]
b. rem = sum % k
c. If firstSeen contains rem:
- If i - firstSeen[rem] >= 2: return true
- (Do not update firstSeen[rem])
d. Else: firstSeen[rem] = i
4. Return false其他解法
替代方案
方案一：暴力枚舉所有子陣列
雙重迴圈枚舉所有長度 ≥ 2 的子陣列，計算其和並檢查是否為 k 的倍數。可用前綴和陣列避免重複計算。
- 優點：思路直觀，無需理解同餘定理。
- 缺點：時間複雜度 O(n²)，空間 O(n)（前綴和陣列），在 n 較大時（如 10^5）會超時。
方案二：滑動窗口（不適用）
滑動窗口適合解決「子陣列和等於某值」且元素非負的情況。但本題中元素可為負數，窗口大小不單調，無法直接使用滑動窗口。
方案三：前綴和陣列 + 集合
預先計算所有前綴和 mod k，存入陣列，然後雙重迴圈比較任意兩個前綴和的餘數。
- 優點：邏輯清晰，與 HashMap 解法等價。
- 缺點：時間 O(n²)，沒有利用 HashMap 的 O(1) 查詢優勢；不如直接用 HashMap 解法。
延伸思考
延伸問題
-
子陣列和恰好為 k 的倍數的個數：若要計算所有滿足條件的子陣列數（而非只判斷是否存在），改用
count[rem]記錄每個餘數出現的次數，當遇到相同餘數時加上之前的 count 值。這是 LC 974（Subarray Sums Divisible by K）的題目。 -
移除長度限制：若子陣列長度可以為 1（即單個元素也算），只需初始化時移除
firstSeen[0] = -1的長度限制，改為檢查i - firstSeen[rem] >= 1，或改用 count 統計法。 -
負數元素的挑戰：本題
nums[i] >= 0，但若允許負數，前綴和可能超出 [0, k-1] 範圍（C++ 的%對負數結果為負）。需要用((sum % k) + k) % k確保餘數始終非負，這是使用同餘定理時的常見陷阱。