Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/description/

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

Note:

The length of the array is in range [1, 20,000].

The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Thoughts

统计所有满足和为K的子数组数目。subarray sum问题无非用presum或DP。这道题和普通subarray sum区别前者统计频率，后者只是问是否存在，思路一致的，对每个presum记录下频率。

Code

/*
 * @lc app=leetcode id=560 lang=cpp
 *
 * [560] Subarray Sum Equals K
 */

// @lc code=start
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> presum;
        presum[0] = 1;
        int s = 0, res = 0;
        for (const auto num : nums) {
            s += num;
            if (presum.count(s - k)) res += presum[s - k];
            if (!presum.count(s)) presum[s] = 0;
            ++presum[s]; 
        }
        return res;
    }
};
// @lc code=end

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> sums = new HashMap<>();
        sums.put(0, 1);
        int res = 0;
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sums.containsKey(sum - k)) {
                res += sums.get(sum - k); 
            }
            sums.put(sum, sums.getOrDefault(sum, 0) + 1);
        }

        return res;
    }
}

Analysis

时间复杂度O(N), 空间O(N).