Subarray Sum Equals K
MedPrompt
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to consider every possible subarray, calculate its sum, and check if the sum equals k. We can optimize the sum calculation by iterating through all possible start points and for each start point, extending the subarray to the right while keeping a running sum.
Algorithm
- Initialize a counter
countto 0. - Use an outer loop with index
startfrom 0 ton-1to select the starting element of the subarray. - Inside the outer loop, initialize a
currentSumto 0. - Use an inner loop with index
endfromstartton-1. This loop defines the end of the subarray. - In each step of the inner loop, add
nums[end]tocurrentSum. ThiscurrentSumrepresents the sum of the subarraynums[start...end]. - If
currentSumis equal tok, incrementcount. - After both loops complete, return
count.
Walkthrough
This approach iterates through all possible starting points of a subarray. For each starting point, it iterates through all possible ending points, effectively generating every contiguous subarray. A running sum is maintained for the current subarray, and if this sum equals k, a counter is incremented.
public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int currentSum = 0; for (int end = start; end < nums.length; end++) { currentSum += nums[end]; if (currentSum == k) { count++; } } } return count;}Complexity
Time
O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic runtime, which is too slow for the given constraints.
Space
O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space (O(1) space complexity).
Cons
Inefficient time complexity, leading to "Time Limit Exceeded" on larger test cases as per the problem constraints.
This is the most efficient approach, utilizing a hash map to store prefix sums and their frequencies. The core idea is that if the cumulative sum up to two indices i and j (where i < j) is sum_i and sum_j respectively, then the sum of the subarray between i and j is sum_j - sum_i. We are looking for subarrays where sum_j - sum_i = k, which can be rewritten as sum_i = sum_j - k.
Algorithm
- Initialize
count = 0andcurrentSum = 0. - Create a hash map
prefixSumMapto store the frequency of each prefix sum encountered. - Put an initial entry
(0, 1)into the map. This handles cases where a subarray starting from index 0 sums tok. - Iterate through the
numsarray. For each numbernum:- Add
numtocurrentSum. - Check if
prefixSumMapcontains the keycurrentSum - k. If it does, it means there areprefixSumMap.get(currentSum - k)subarrays ending at the current position that sum tok. Add this frequency tocount. - Update the frequency of the
currentSumin theprefixSumMap. Increment its count by 1.
- Add
Walkthrough
By iterating through the array, we can maintain the current prefix sum. For each element, we calculate the currentSum. Then, we check if currentSum - k exists in our hash map. If it does, it means there's a previous prefix sum that, when subtracted from the currentSum, gives k. The number of times currentSum - k has occurred corresponds to the number of new subarrays ending at the current position with a sum of k. We then update the map with the currentSum.
import java.util.HashMap;import java.util.Map; public int subarraySum(int[] nums, int k) { int count = 0; int currentSum = 0; Map<Integer, Integer> prefixSumMap = new HashMap<>(); // Base case: a prefix sum of 0 has occurred once (the empty prefix) prefixSumMap.put(0, 1); for (int num : nums) { currentSum += num; // Check if a subarray ending here sums to k // This is equivalent to finding a previous prefix sum `p` such that `currentSum - p = k` // or `p = currentSum - k` if (prefixSumMap.containsKey(currentSum - k)) { count += prefixSumMap.get(currentSum - k); } // Add the current prefix sum to the map prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1); } return count;}Complexity
Time
O(n), where n is the length of `nums`. We iterate through the array only once. Hash map operations (put and get) take constant time on average.
Space
O(n), as the hash map can store up to `n` distinct prefix sums in the worst case where all prefix sums are unique.
Trade-offs
Pros
Highly efficient with linear time complexity.
Solves the problem within the given constraints.
Cons
Requires extra space for the hash map, which can be up to O(n) in the worst case.
The logic is slightly more complex to grasp compared to the brute-force method.
Solutions
Solution
class Solution {public int subarraySum(int[] nums, int k) { Map<Integer, Integer> counter = new HashMap<>(); counter.put(0, 1); int ans = 0, s = 0; for (int num : nums) { s += num; ans += counter.getOrDefault(s - k, 0); counter.put(s, counter.getOrDefault(s, 0) + 1); } return ans; }}class Solution {public: int subarraySum(vector<int> &nums, int k) { unordered_map<int, int> counter; counter[0] = 1; int ans = 0, s = 0; for (int &num : nums) { s += num; ans += counter[s - k]; ++counter[s]; } return ans; }};class Solution: # not matter if the same num like [1,1] dp [ s ] += 1 return ans ############# class Solution : # over time limit, not fast enough def subarraySum ( self , nums : List [ int ], k : int ) -> int : count = 0 # sum value from 1 to i-th element sum_arr = [ 0 ] * ( len ( nums ) + 1 ) # cached sum for i in range ( 1 , len ( nums ) + 1 ): sum_arr [ i ] = sum_arr [ i - 1 ] + nums [ i - 1 ] for start in range ( len ( nums )): for end in range ( start + 1 , len ( nums ) + 1 ): if sum_arr [ end ] - sum_arr [ start ] == k : count += 1 return count def subarraySum(self, nums: List[int], k: int) -> int: dp = Counter({0: 1}) ans = s = 0 for num in nums: s += num ans += dp[s - k]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.