523. Continuous Subarray Sum

Medium

Description

給定整數陣列 nums 和整數 k，判斷是否存在長度至少為 2 的連續子陣列，其元素和為 k 的倍數（包含 0）。

Example:

Input: nums = [23,2,4,6,7], k = 6 Output: true （[2,4] 的和為 6，是 6 的倍數）

Intuition#

核心思路：利用前綴和取餘的性質——若 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#

概念: 枚舉所有長度 >= 2 的子陣列，計算和並檢查是否為 k 的倍數
時間複雜度: O(n^2) - 雙層迴圈
空間複雜度: 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#

概念: 維護前綴和 mod k，用 HashMap 記錄每個餘數首次出現的索引，若相同餘數再次出現且距離 >= 2 則回傳 true
時間複雜度: O(n) - 一次遍歷
空間複雜度: 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
    }
}

初始化 remainderIndex[0] = -1 很關鍵：它處理了「從 index 0 開始的子陣列本身就是 k 的倍數」的情況。另外，只保留餘數首次出現的索引（不更新），才能確保找到的子陣列長度 >= 2。

🔑 Takeaways#

Pattern: 子陣列和整除問題 -> 前綴和 mod + HashMap
關鍵技巧: 同餘原理（prefixSum[j] % k == prefixSum[i] % k => sum(i+1..j) % k == 0）是這類問題的數學基礎；初始化 {0: -1} 處理邊界