560. Subarray Sum Equals K

紀錄一段連續的子數組加總等於k, 我光暴力法都沒頭緒了

暴力法就是, 先把每層都累加起來, 累加完後, 假設在累加的過程, 找得到兩數相減等於k的, 就代表,這兩個index之間的總和為k

暴力法會TLE

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(nums.size() ==0 )return 0;
        vector<int> sum_vec(nums.size(), 0);
        sum_vec[0] = nums[0];
        int res = 0;
        for(int i = 1; i < nums.size();i++){
            sum_vec[i] += nums[i] + sum_vec[i-1];
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (sum_vec[i] == k) ++res;
            for (int j = i - 1; j >= 0; --j) {
                if (sum_vec[i] - sum_vec[j] == k) ++res;
            }
        }
        
        return res;
    }
};

另一種做法就是用hash map紀錄加總過的數字, 直接用map找會比較快

我看完解答後, 有件事情不能理解, 為什麼我們不用set然後只要發現我sum-k在set裡找的到 res直接加一就行了

class Solution {
public:
    int subarraySum(vector<int>& n, int k) {
        int res = 0, sum = 0; 
        unordered_set<int> m; 
        m.insert(0);
        for (int i = 0; i < n.size(); i++) {
            sum += n[i]; 
            if (m.count(sum-k)) 
                res ++; 
            m.insert(sum);
        }
        return res;
    }
};

原因是, 這樣最大的數量就只有整個array的長度, 但實際上, 子數組應該存在更多的可能

[-1, 1, 0, 0] 存在 6種, 用上面的方法只找得到後面三種

所以我們得在算完[-1, 1, 0]的結果, 把他數量記起來, 在當第四個零在參考的時候, 他可以這麼做

[-1,1,0,0] or [0,0] or [0] 

等於是0的結果會再多一種, 我們會再把他加到0的總數裡

我覺得這沒有很好想誒XD, 但就先記下來吧

class Solution {
public:
    int subarraySum(vector<int>& n, int k) {
        int res = 0, sum = 0; 
        unordered_map<int, int> m; 
        m[0] = 1;
        for (int i = 0; i < n.size(); i++) {
            sum += n[i]; 
            if (m.count(sum-k)) 
                res += m[sum - k]; 
            m[sum]++;
        }
        return res;
    }
};