560. 和為 K 的子數組

思路

給定一個數組 $[10,0,-20,20,-20]$，target = 0，求元素總和為target的最長子數組。
如果單純用前綴數組，需要 $O(n^2)$的複雜度去找到所有子數組的總和，依舊太慢，需要優化。

範例的前綴數組是 $[\orange0,10,10,-10,10,-10]$，
對於第一個 $-10$來說，前面需要 $10$跟它配對成目標數字 $0$，
而在它前面有兩個 $10$。所以答案 +2 。
對第二個 $-10$來說，同樣需要前面有幾個 $10$。
因此使用哈希表去紀錄出現次數，遇到能配對的數字，就將答案加上該數字的出現次數。

程式碼

前綴和

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        int res = 0, sum = 0;
        freq[0]++; // 0 最一開始就出現了
        for(int x : nums) {
            sum += x;
            if(freq.contains(sum - k)) { // 配對的數字有出現過
                res += freq[sum - k];
            }
            freq[sum]++;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$