560. Subarray Sum Equals K

Medium

Description

給定整數陣列 nums 和整數 k，回傳和等於 k 的連續子陣列的數量。

Example:

Input: nums = [1,1,1], k = 2 Output: 2

Intuition#

核心思路：Prefix Sum + HashMap。如果 prefix[j] - prefix[i] == k，則子陣列 [i+1, j] 的和為 k。用 HashMap 記錄每個前綴和出現的次數。

暴力法需要 O(n^2) 枚舉所有子陣列
利用前綴和的性質：sum(i,j) = prefix[j] - prefix[i]
遍歷時查找 prefix[j] - k 在之前出現了幾次

Approaches#

1: Brute Force#

概念: 枚舉所有子陣列的起點和終點，計算和
時間複雜度: O(n^2) - 兩層迴圈
空間複雜度: O(1)

class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        var count = 0
        for (i in nums.indices) {
            var sum = 0
            for (j in i until nums.size) {
                sum += nums[j]
                if (sum == k) count++
            }
        }
        return count
    }
}

⭐2: Prefix Sum + HashMap#

概念: 維護前綴和 sum，用 HashMap 記錄每個前綴和出現的次數。每到一個位置，查找 sum - k 出現了幾次
時間複雜度: O(n) - 一次遍歷
空間複雜度: O(n) - HashMap

class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        val prefixCount = HashMap<Int, Int>()
        prefixCount[0] = 1  // 空前綴
        var sum = 0
        var count = 0

        for (num in nums) {
            sum += num
            count += prefixCount.getOrDefault(sum - k, 0)
            prefixCount[sum] = (prefixCount[sum] ?: 0) + 1
        }

        return count
    }
}

初始化 prefixCount[0] = 1 很重要，代表「空前綴」，用於處理從索引 0 開始的子陣列和恰好等於 k 的情況。

🔑 Takeaways#

Pattern: Prefix Sum + HashMap 是解決「子陣列和等於 K」的標準模式
關鍵技巧: 不能用 Sliding Window，因為元素可能為負數（窗口擴大/縮小不保證單調性）；prefixCount[0] = 1 是常見的初始化陷阱