前言

嘿嘿～今天要解一道看起來有點複雜但其實可以很簡單的題目，叫做 Subarray Sum Equals K（子陣列和等於 K）。
這題的意思是，我們有一個整數陣列 nums，還有一個數字 k，我們要找出這個陣列裡有多少段連續的數字加起來剛好等於 k。

說白了，就是找出有幾段連續的數字，它們的總和等於 k。
連續的意思是，不能跳過中間的數字哦！

題目 Subarray Sum Equals K

難度：Medium

題目描述：

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

給你一個整數陣列 nums 和一個整數 k，要你返回有多少個連續子陣列的總和等於 k。

範例 1：

輸入： nums = [1, 1, 1]，k = 2

輸出： 2

解釋： 這個陣列有兩段子陣列的和等於 2，那就是 [1, 1] 出現了兩次（一次是從索引 0 到 1，另一次是從索引 1 到 2）。

範例 2：

輸入： nums = [1, 2, 3]，k = 3

輸出： 2

解釋： 這裡有兩段子陣列的和等於 3，分別是 [1, 2] 和 [3]。

中文描述

給定一個整數陣列 nums 和一個整數 k，返回陣列中有多少段連續子陣列的和等於 k。

實作

要解這個問題，我們可以使用「前綴和」這個概念來優化運算。簡單來說，我們可以先累積每個數字的總和，然後再找出符合條件的子陣列，而不需要每次重新計算每個子陣列的和。

具體做法是這樣的：

function subarraySum(nums: number[], k: number): number {
    let count = 0; // 記錄總共有多少個符合條件的子陣列
    let sum = 0; // 記錄目前累積到的總和
    const map = new Map%3Cnumber, number%3E(); // 用來記錄每個總和出現了幾次
    map.set(0, 1); // 當總和是 0 時，代表一開始就有可能符合條件的子陣列

    for (let num of nums) {
        sum += num; // 逐步累積總和

        // 看看是否存在 sum - k 這樣的總和，如果有，代表找到符合條件的子陣列
        if (map.has(sum - k)) {
            count += map.get(sum - k)!; // 把出現的次數加到計數裡
        }

        // 把當前的總和記錄到 map 裡，如果之前有相同的總和，次數加一
        map.set(sum, (map.get(sum) || 0) + 1);
    }

    return count; // 返回符合條件的子陣列數量
}

解題心法

1. 前綴和是什麼？

   前綴和的意思就是，從陣列的起點開始，逐個數字累加。比如陣列是 [1, 2, 3]，那它的前綴和就是 [1, 3, 6]。每個數字都表示到當前為止的總和。

2. 怎麼找符合條件的子陣列？

   當我們找到某個前綴和 sum，如果之前曾經出現過 sum - k，那麼從那個時候到現在的這段子陣列的和就是 k。所以，我們只要記住每個總和出現的次數，就可以快速知道有多少段子陣列的和等於 k。

3. 用哈希表來加速查找：

   我們可以用一個哈希表來記錄每個前綴和出現的次數，這樣每次查找和更新的時間複雜度都是 O(1)。而我們遍歷整個陣列的時間是 O(n)，因此整體的時間複雜度是 O(n)。

為什麼這樣處理？

這種解法利用了前綴和來避免重複計算，並通過哈希表快速查找是否有符合條件的子陣列，這樣可以大幅減少運算時間，讓我們可以在 O(n) 的時間內解決問題，優化了效率。

本次要點：

• 前綴和讓我們可以只累加一次數字就知道從頭到某個位置的總和。
• 用哈希表記錄前綴和出現的次數，這樣可以快速找到是否有符合條件的子陣列。
• 確保每次加總和查找都是 O(1) 的運算，使整體時間複雜度保持在 O(n)。

子陣列的定義：

子陣列（Subarray）是指一個陣列中的連續部分。
這意味著，子陣列必須是從原陣列中挑選出來的一段連續元素，順序不能改變，也不能跳過中間的元素。

-子陣列的特點

• 子陣列中的元素必須是連續的，不能跳過或重排。
• 子陣列可以包含原陣列的所有元素，也可以是只包含一部分元素，甚至可以是只有一個元素。
• 每個陣列都有很多子陣列，比如一個包含 3 個元素的陣列 [1, 2, 3]，它的子陣列可以是：
  • [1]
  • [2]
  • [3]
  • [1, 2]
  • [2, 3]
  • [1, 2, 3]

舉例：

假設有一個陣列 nums = [1, 2, 3, 4]，它的子陣列包括：

• 單個元素的子陣列：[1], [2], [3], [4]
• 兩個元素的子陣列：[1, 2], [2, 3], [3, 4]
• 三個元素的子陣列：[1, 2, 3], [2, 3, 4]
• 整個陣列：[1, 2, 3, 4]

子陣列強調的是連續性，與子集不同。子集中的元素可以不連續、無序排列，而子陣列的順序必須與原陣列相同。

與子序列（Subsequence）的區別：

• 子陣列：要求元素必須連續。
• 子序列：元素不必連續，但順序不能改變。

本次解題要點：

1. 子陣列：必須是連續的一段元素，不能跳過或改變順序。
2. 前綴和：累積每個位置之前的總和，幫助快速判斷子陣列的總和。
3. 哈希表加速：用哈希表來記錄前綴和出現的次數，能夠快速查找是否有符合條件的子陣列。
4. 優化效率：透過前綴和和哈希表的結合，將運算時間優化為 O(n)。

這樣了解過後是不是覺得這題沒那麼可怕啦！
學會這個技巧後，處理子陣列問題變得更加簡單了～
下次再一起挑戰更多有趣的題目吧！٩(●˙▿˙●)۶…⋆ฺ

明天颱風假放假，開心❤️再繼續刷題吧...