LeetCode: Subarray Sum Equals K Posted on March 14, 2018July 26, 2020 by braindenny Subarray Sum Equals K Similar Problems: LeetCode: Number of Submatrices That Sum to Target Minimum Size Subarray Sum Binary Subarrays With Sum CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #hashmap, #subarray, #presum 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]. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/subarray-sum-equals-k ## Basic Ideas: presum + hashmap ## ## Complexity: Time O(n), Space O(n) class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # value -> count freqs = collections.defaultdict(int) freqs[0] = 1 n = len(nums) res, presum = 0, 0 for i in range(n): presum += nums[i] res += freqs[presum-k] freqs[presum] += 1 return res // https://code.dennyzhang.com/subarray-sum-equals-k // Basic Ideas: Presum + Dynamic Programming // Count how many subarray ends with current item // Complexity: Time O(n), Space (n) func subarraySum(nums []int, k int) int { res, preSum := 0, 0 h := map[int]int{0: 1} for _, v := range nums { preSum += v res += h[preSum - k] h[preSum]++ } return res } Post Views: 8