[LeetCode] 560. Subarray Sum Equals K

[frdmu]

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

解法一：
使用前缀和， 但是会超时，代码如下:

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

解法二：
优化解法一，采用hashtable记录前缀和出现的次数，代码如下：

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

类似题目：
930. Binary Subarrays With Sum