題目： LeetCode - 560. Subarray Sum Equals K

題目說明

給一個陣列及一個 k，求陣列中連續子陣列的和等於 k 的個數。

解題思路

使用一個迴圈，sum 為從 nums[0] 加到當前元素的值，使用 unordered_map<int, int> 紀錄子陣列和出現的次數。對於 sum 來說，每次得到新的 sum 時，若是前面的子陣列和有出現 sum - k 的話，代表新的子陣列和減掉舊的子陣列和就會得到 k，所以每次迴圈 count 都加上 hash[sum - k]，最後回傳 count 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if(!n)
            return 0;
        unordered_map<int, int> hash;
        hash.reserve(n);
        int count = 0, sum = 0;
        for(auto& i : nums)
        {
            ++hash[sum];
            sum += i;
            count += hash[sum - k];
        }
        return count;
    }
};

補充

++hash[sum] 放在前面做是因為要在裡面放入 {0, 1}，代表子陣列和為 0 會出現一次。因為每次得到新的 sum 時，只會調用到 hash[sum - k]，所以直接把它放到前面做。