Subarray Sum Equals K

mediumFREEArrays & StringsMeta DSA

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

Example

Input

1,1,1
2

Output

Reasoning

The input array is [1, 1, 1] and the target sum k is $2$ .
We can calculate the sum of all possible subarrays: [1] sums to $1$ , [1, 1] sums to $2$ , [1, 1, 1] sums to $3$ , and [1, 1] and [1, 1] (the second and third elements) also sum to $2$ .
The subarrays that sum to $k = 2$ are [1, 1] (first and second elements) and [1, 1] (second and third elements).
The total number of subarrays whose sum equals $k$ is $2$ .

Constraints

1 <= len(nums) <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Meta DSA

Valid Palindrome IIeasy Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium

Concept primer

Background Knowledge

The problem "Subarray Sum Equals K" involves finding the total number of subarrays in a given array nums whose sum equals a target value k. This problem is a classic example of a subarray problem, which is a common theme in array and string problems. To tackle this problem, it's essential to understand the concept of prefix sums, which can help in efficiently calculating the sum of subarrays. The idea of prefix sums is to calculate the cumulative sum of the array elements from the beginning to each index.

The concept of hashing is also crucial in solving this problem. Hashing allows us to store and retrieve elements efficiently, which can be particularly useful when dealing with large datasets. In the context of this problem, hashing can help us keep track of the prefix sums we've seen so far and their corresponding frequencies. This can enable us to quickly identify subarrays with a sum equal to k. Understanding how to utilize hashing to store and retrieve prefix sums is vital to developing an efficient solution.

Another key concept is the idea of sliding windows, which is a common technique used in array and string problems. Although the traditional sliding window approach might not be directly applicable here, the idea of maintaining a window of elements and adjusting it based on certain conditions can be useful. In this case, we're not necessarily dealing with a fixed-size window, but rather, we're interested in finding all possible subarrays that meet the given condition.

Algorithm/Approach

The algorithmic approach to solve this problem involves using a combination of prefix sums and hashing. The general idea is to calculate the prefix sums of the array and store them in a hash map along with their frequencies. Then, for each prefix sum, we check if there exists a previous prefix sum such that the difference between the two sums equals k. If such a pair is found, it means we've identified a subarray with a sum equal to k.

Step-by-Step Strategy

To implement the solution, follow these steps:

Calculate the prefix sums of the array and store them in a hash map along with their frequencies.
Iterate through the array, and for each prefix sum, check if there exists a previous prefix sum such that the difference between the two sums equals k.
If such a pair is found, increment the count of subarrays with a sum equal to k.
Finally, return the total count of subarrays with a sum equal to k.

Common Pitfalls

When implementing the solution, watch out for the following:

Make sure to handle edge cases, such as an empty array or k being zero.
Be careful when calculating the prefix sums, as integer overflow can occur for large arrays.
Ensure that the hash map is properly updated and queried to avoid incorrect results.

Time & Space Complexity

The expected time complexity for this problem is O(n), where n is the length of the array, since we're iterating through the array once. The space complexity is also O(n), as in the worst case, we might need to store all prefix sums in the hash map.

solution.py

Python 3.13

Test results