給定整數陣列
nums和整數k，回傳和等於k的連續子陣列的數量。
Example:
Input: nums = [1,1,1], k = 2 Output: 2
Intuition
TIP
核心思路：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)
- Idea: 枚舉所有子陣列的起點和終點，計算和
- Time:
O(n^2)- 兩層迴圈 - Space:
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 — O(n) / O(n)
- Idea: 維護前綴和
sum，用 HashMap 記錄每個前綴和出現的次數。每到一個位置，查找sum - k出現了幾次 - Time:
O(n)- 一次遍歷 - Space:
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
}
}WARNING
初始化 prefixCount[0] = 1 很重要，代表「空前綴」，用於處理從索引 0 開始的子陣列和恰好等於 k 的情況。
🔑 Takeaways
- Pattern: Prefix Sum + HashMap 是解決「子陣列和等於 K」的標準模式
- Key trick: 不能用 Sliding Window，因為元素可能為負數（窗口擴大/縮小不保證單調性）；
prefixCount[0] = 1是常見的初始化陷阱