題目說明

560. Subarray Sum Equals K
     給定一個整數陣列 nums 和整數 k，請你找出 和為 k 的連續子陣列的個數。

範例

Input: nums = [1,1,1], k = 2
Output: 2
解釋：連續子陣列 [1,1] 出現兩次

Input: nums = [1,2,3], k = 3
Output: 2
解釋：子陣列 [1,2] 與 [3]

Python 解法（前綴和 + 哈希表）

def subarraySum(nums, k):
count = 0
curr_sum = 0
prefix = {0: 1} # 初始化，sum為0出現一次
for num in nums:
curr_sum += num
if curr_sum - k in prefix:
count += prefix[curr_sum - k]
prefix[curr_sum] = prefix.get(curr_sum, 0) + 1
return count

Java 解法（前綴和 + 哈希表）

import java.util.*;
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, currSum = 0;
Map<Integer, Integer> prefix = new HashMap<>();
prefix.put(0, 1);
for (int num : nums) {
currSum += num;
if (prefix.containsKey(currSum - k)) count += prefix.get(currSum - k);
prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);
}
return count;
}
}

Java vs Python 差異
• Python 用 .get(curr_sum, 0) 簡化取值與初始化，Java 用 getOrDefault
• 核心邏輯都是 前綴和 + 哈希表計數，用來快速找出和為 k 的子陣列
• Python 程式碼短，Java 稍長但概念一致

複雜度分析
• 時間複雜度：O(n)，每個元素只訪問一次
• 空間複雜度：O(n)，哈希表存儲前綴和出現次數