560. Subarray Sum Equals K

題目理解

題目連結: Subarray Sum Equals K

這道題目要求找出陣列中和為 k 的子陣列數量

範例:

輸入: nums = [1,1,1], k = 2
輸出: 2
解釋: 此題有兩個和為 2 的子陣列：[1,1] 與 [1,1]

解題思路

Brute Force

最直觀的解法是使用暴力方法 (Brute Force)。具體步驟如下：

1. 遍歷所有可能的子陣列：
   • 使用兩個嵌套的 for 迴圈，第一個迴圈固定子陣列的起始位置，第二個迴圈固定子陣列的結束位置。
   • 計算從起始位置到結束位置的所有元素之和
   • 如果這個和等於 k，則計數器加一

這種方法的時間複雜度是 O(n^2)，因為需要遍歷所有可能的子陣列並計算其和

prefix sum 與 hash table

具體步驟如下：

1. 計算前綴和： 我們遍歷陣列，將當前元素與之前的元素相加，得到當前的前綴和。如果這個前綴和等於 k，則表示從陣列開頭到當前元素的子陣列和等於 k
2. 使用 hash table 記錄前綴和的出現次數： 我們使用一個 hash table 來記錄前綴和出現的次數。這樣當遍歷到某個元素時，我們可以通過查詢 hash table 來判斷是否存在某個之前的前綴和，使得當前的前綴和減去這個之前的前綴和等於 k

具體實現

1. 計算前綴和： 在第一個 for 迴圈中，將每個元素加上其前一個元素，這樣就計算出了從陣列開頭到當前元素的前綴和
2. 初始化 hash table： 使用 unordered_map 來記錄前綴和的出現次數。這樣在第二個 for 迴圈中，我們可以快速查詢是否存在某個前綴和使得當前前綴和減去這個前綴和等於 k
3. 更新 hash table： 在每次迴圈中，將當前的前綴和記錄到 hash table 中，這樣在之後的迴圈中就可以使用這些前綴和來判斷是否存在符合條件的子陣列

複雜度

• Time Complexity：O(n)，其中 n 是陣列的長度。遍歷陣列計算前綴和和使用 hash table 的操作都是線性時間。
• Space Complexity：O(n)，最壞情況下 hash table 中需要存儲所有的前綴和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        const int n = nums.size();

        int ans = nums[0] == k;
        for (int i = 1; i < n; i += 1) {
            nums[i] += nums[i - 1];
            ans += (nums[i] == k);
        }

        unordered_map<int, int> prefix;
        for (int i = 0; i < n; i += 1) {
            if (prefix.count(nums[i] - k)) {
                ans += prefix[nums[i] - k];
            }

            prefix[nums[i]] += 1;
        }
        return ans;
    }
};

class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = nums[0] == k ? 1 : 0;
        for (int i = 1; i < nums.length; i += 1) {
            nums[i] += nums[i - 1];
            if (nums[i] == k) {
                ans += 1;
            }
        }

        HashMap<Integer, Integer> prefix = new HashMap<>();
        for (int i = 0; i < nums.length; i += 1) {
            if (prefix.containsKey(nums[i] - k)) {
                ans += prefix.get(nums[i] - k);
            }
            prefix.put(nums[i], prefix.getOrDefault(nums[i], 0) + 1);
        }
        return ans;
    }
}