給定整數陣列
nums和整數k，判斷是否存在長度至少為 2 的連續子陣列，其元素和為k的倍數（包含 0）。
Example:
Input: nums = [23,2,4,6,7], k = 6 Output: true （[2,4] 的和為 6，是 6 的倍數）
Intuition
TIP
核心思路：利用前綴和取餘的性質——若 prefixSum[j] % k == prefixSum[i] % k，則 sum(i+1..j) 是 k 的倍數。用 HashMap 記錄每個餘數首次出現的索引。
sum(i+1..j) = prefixSum[j] - prefixSum[i]- 若兩者 mod k 相同，差值就是 k 的倍數
- 需要子陣列長度 >= 2，所以要確保
j - i >= 2 - HashMap 存餘數到「最早出現的索引」，因為我們要最大化
j - i
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 枚舉所有長度 >= 2 的子陣列，計算和並檢查是否為 k 的倍數
- Time:
O(n^2)- 雙層迴圈 - Space:
O(1)- 不需額外空間
class Solution {
fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
for (i in nums.indices) {
var sum = nums[i]
for (j in i + 1 until nums.size) {
sum += nums[j]
if (sum % k == 0) return true
}
}
return false
}
}⭐ 2. Prefix Sum Mod + HashMap — O(n) / O(min(n, k))
- Idea: 維護前綴和 mod k，用 HashMap 記錄每個餘數首次出現的索引，若相同餘數再次出現且距離 >= 2 則回傳 true
- Time:
O(n)- 一次遍歷 - Space:
O(min(n, k))- HashMap 最多 k 個不同餘數
class Solution {
fun checkSubarraySum(nums: IntArray, k: Int): Boolean {
// 餘數 -> 首次出現的索引
// 初始化 0 -> -1，代表前綴和為 0 在 index -1 處
val remainderIndex = HashMap<Int, Int>()
remainderIndex[0] = -1
var prefixMod = 0
for (i in nums.indices) {
prefixMod = (prefixMod + nums[i]) % k
if (remainderIndex.containsKey(prefixMod)) {
if (i - remainderIndex[prefixMod]!! >= 2) {
return true
}
// 不更新，保留最早的索引
} else {
remainderIndex[prefixMod] = i
}
}
return false
}
}WARNING
初始化 remainderIndex[0] = -1 很關鍵：它處理了「從 index 0 開始的子陣列本身就是 k 的倍數」的情況。另外，只保留餘數首次出現的索引（不更新），才能確保找到的子陣列長度 >= 2。
🔑 Takeaways
- Pattern: 子陣列和整除問題 -> 前綴和 mod + HashMap
- Key trick: 同餘原理（
prefixSum[j] % k == prefixSum[i] % k=>sum(i+1..j) % k == 0）是這類問題的數學基礎；初始化{0: -1}處理邊界