560. Subarray Sum Equals K
https://leetcode.com/problems/subarray-sum-equals-k/
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].
---
Intuition
If prefixSum[j] - prefixSum[i] == 0 => elements i..j did not change prefix sum => sum(arr[i...j]) = 0
Extending this
If prefixSum[j] - prefixSum[i] == k => sum(arr[i...j]) = k
Track prefixSum, and # of times it occurs in HashMap
Iterate through the array
Compute prefix sum
# of times (prefixSum - k) has occurred up-to this point = # of times subarrays sum to k before current => add to answer
Update hashmap with freq of current prefix Sum
---
Time - O(n)
Space - O(n)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int subarraySum(int[] nums, int k) { | |
| int ans = 0; | |
| Map<Integer, Integer> sumFreq = new HashMap<Integer, Integer>(); | |
| // Initialize 0 prefix sum, occurred once | |
| sumFreq.put(0, 1); | |
| int sum = 0; | |
| for (int num: nums) { | |
| sum += num; | |
| // subarrays with sum between sum and sum - k, sum to k | |
| ans += sumFreq.getOrDefault(sum - k, 0); | |
| // capture sub arrays cumulative sum freq | |
| sumFreq.put(sum, sumFreq.getOrDefault(sum, 0) + 1); | |
| } | |
| return ans; | |
| } | |
| } |
