題目
#

leetcode 560 - Subarray Sum Equals K (題目說明請點連結)

題目簡述
#

給定一個整數陣列和一個整數 k，找到該陣列中和為 k 的連續子陣列的個數。

範例
#

Example 1:

Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: 有兩個子數組的和為 2：[1,1] 和 [1,1]。

Example 2:

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: 有兩個子數組的和為 3：[1,2] 和 [3]。

解題思路
#

這題目要求我們找出數組中和為 k 的子數組的個數。可以使用 前綴和 和 HashMap 來解決這個問題，這樣能夠高效處理，時間複雜度為 O(n)。

什麼是前綴和與HashMap
#

前綴和（Prefix Sum） 其實就是從數組的開頭開始，累加每一個數字，直到某個位置。對於數組中的任意子數組 [i, j]，它的和其實就是 sum[j] - sum[i-1]，其中 sum[i-1] 表示從頭到 i-1 的和。

舉個例子，假設有一個數組 nums = [2, 3, 1, 4]，我們可以計算它的前綴和陣列 sum 為：

sum[0] = 2
sum[1] = 2 + 3 = 5
sum[2] = 2 + 3 + 1 = 6
sum[3] = 2 + 3 + 1 + 4 = 10

如果我們想知道 nums[1] 到 nums[3]（也就是 [3, 1, 4]）的和是多少，可以用 sum[3] - sum[0] = 10 - 2 = 8，這就是前綴和的應用。

我們的目標是找到一組子數組，使得它們的和為 k。所以每當我們累加一個數字時，我們就去查HashMap中是否存在 total - k，如果存在，則說明這個位置之前的某個地方到現在的位置的子數組和正好是 k。

解法
#

每次遍歷到一個數字時，把它加到目前的總和 total，然後去HashMap裡查有沒有 total - k 這個值。如果有，代表之前某個位置到現在的子數組和剛好是 k，那就把這個值在HashMap出現的次數加到答案裡。
為了確保能計算從陣列開頭開始的子數組，我們一開始就把HashMap設成 map = {0: 1}，這樣如果一開始的總和就等於 k，也能正確計算進去。

例子說明
#

nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7

初始情況：map = {0: 1}, total = 0, result = 0

處理第一個數字 3：
- total = 3
- 查HashMap map 是否有 3 - 7 = -4，沒有。
- 更新 map，map = {0: 1, 3: 1}。
處理第二個數字 4：
- total = 7
- 查HashMap map 是否有 7 - 7 = 0，找到了，map.get(0) = 1，結果 result += 1，result = 1。
- 更新 map，map = {0: 1, 3: 1, 7: 1}。
處理第三個數字 7：
- total = 14
- 查HashMap map 是否有 14 - 7 = 7，找到了，map.get(7) = 1，結果 result += 1，result = 2。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 1}。
處理第四個數字 2：
- total = 16
- 查HashMap map 是否有 16 - 7 = 9，沒有找到。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 1, 16: 1}。
處理第五個數字 -3：
- total = 13
- 查HashMap map 是否有 13 - 7 = 6，沒有找到。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 1, 16: 1, 13: 1}。
處理第六個數字 1：
- total = 14
- 查HashMap map 是否有 14 - 7 = 7，找到了，map.get(7) = 1，結果 result += 1，result = 3。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 2, 16: 1, 13: 1}。
處理第七個數字 4：
- total = 18
- 查HashMap map 是否有 18 - 7 = 11，沒有找到。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 2, 16: 1, 13: 1, 18: 1}。
處理第八個數字 2：
- total = 20
- 查HashMap map 是否有 20 - 7 = 13，找到了，map.get(13) = 1，結果 result += 1，result = 4。
- 更新 map，map = {0: 1, 3: 1, 7: 1, 14: 2, 16: 1, 13: 1, 18: 1, 20: 1}。

最終結果是 4，即有四個子數組的和為 7。

完整程式碼
#

java

import java.util.HashMap;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int result = 0, total = 0; // 初始化結果和累計和
        HashMap<Integer, Integer> map = new HashMap<>(); // 創建HashMap存儲前綴和及其出現次數
        map.put(0, 1); // 初始化，確保能計算從開頭開始的子數組

        for (int num : nums) { // 遍歷數組中的每個數字
            total += num; // 累加當前數字到總和
            if (map.containsKey(total - k)) { // 檢查是否存在前綴和等於total-k
                result += map.get(total - k); // 如果存在，將出現次數加到結果中
            }
            map.put(total, map.getOrDefault(total, 0) + 1); // 更新當前前綴和的出現次數
        }

        return result; // 返回結果
    }
}