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: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107Problem Overview: Given an integer array nums and an integer k, count how many continuous subarrays sum exactly to k. The array can contain negative numbers, so sliding window techniques do not work reliably. You need a method that checks every possible subarray sum efficiently.
Approach 1: Brute Force with Running Sum (O(n²) time, O(1) space)
Iterate over every possible starting index of a subarray. From each start position, extend the subarray to the right while maintaining a running sum. Each time the running sum equals k, increment the count. This avoids recomputing sums from scratch but still checks all O(n²) subarrays. The approach relies only on simple iteration over the array, so space usage remains constant.
This method is straightforward and useful when explaining the problem during an interview. It clearly shows how subarrays are formed and evaluated. However, it becomes slow for large inputs because every start index expands across the remaining array.
Approach 2: Prefix Sum with HashMap (O(n) time, O(n) space)
The optimal approach uses a running prefix sum combined with a frequency map. As you iterate through the array, maintain the cumulative sum up to the current index. If the current prefix sum is curr, then any earlier prefix sum equal to curr - k forms a subarray ending at the current index with sum k. Store counts of prefix sums in a hash table so each lookup runs in O(1).
Initialize the map with {0:1} to handle cases where the subarray starting at index 0 equals k. For each element, update the running sum, check how many times curr - k has appeared, and add that to the result. Then update the frequency of the current prefix sum in the map. This transforms the nested loop into a single linear pass through the array.
Recommended for interviews: Interviewers expect the prefix sum + hash map solution because it reduces the problem from O(n²) to O(n). Starting with the brute force explanation shows you understand the problem space. Moving to prefix sums demonstrates algorithmic optimization and familiarity with hash-based counting patterns that appear in many array problems.
This straightforward approach involves checking all possible subarrays in the given array. We calculate the sum for each subarray and check if it equals k. Although simple, it can be inefficient for large arrays due to its O(n^2) time complexity.
This C code implements a nested loop where the outer loop selects the start of the subarray and the inner loop expands it, calculating the sum. If the sum equals k, it increments the count. The time complexity is O(n^2), and the space complexity is O(1).
Time Complexity: O(n^2)
Space Complexity: O(1)
This optimized approach uses a hashmap to store prefix sums, facilitating the identification of subarrays with the desired sum in constant time. By keeping a count of prefix sums that have been seen, we can determine how many times a specific sum - k has appeared, suggesting that a subarray ending at the current position sums to k.
This C implementation uses a hash table to track the occurrence of prefix sums, adjusted with an offset for negative indices safety, enabling identification of subarrays summing to k. The time complexity reduces to O(n), with space complexity also improving due to the hash table.
Time Complexity: O(n)
Space Complexity: O(n)
We define a hash table cnt to store the number of times the prefix sum of the array nums appears. Initially, we set the value of cnt[0] to 1, indicating that the prefix sum 0 appears once.
We traverse the array nums, calculate the prefix sum s, then add the value of cnt[s - k] to the answer, and increase the value of cnt[s] by 1.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) |
| Approach 2: Using HashMap for Prefix Sums | Time Complexity: O(n) |
| Hash Table + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Running Sum | O(n²) | O(1) | Good for understanding subarray enumeration or when constraints are very small |
| Prefix Sum with HashMap | O(n) | O(n) | General case and expected interview solution for arrays with positive and negative numbers |
Count Subarray sum Equals K | Brute - Better -Optimal • take U forward • 735,816 views views
Watch 9 more video solutions →Practice Subarray Sum Equals K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor