Subarray Sum Equals K
Problem Description
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 <= 107
Solve it on LeetCode
Approaches
1. Brute Force
The brute force approach checks every possible subarray and sums the elements to check if it equals k. This approach is simple to implement but can be inefficient for large arrays.
Intuition:
We iterate through each starting point of a subarray and for each starting point, check every possible end point. This gives us every possible subarray.
Code:
- Time Complexity: O(n^2) - We check every subarray which takes a quadratic amount of time.
- Space Complexity: O(1) - We only use constant space.
2. Prefix Sum Array
We can improve our approach by using a cumulative sum array to keep track of the sum of the elements up to each index.
Intuition:
The cumulative sum array allows us to quickly compute the sum of elements between two indices in constant time by subtracting the cumulative sum of the index before the start of the subarray from the end index.
Code:
- Time Complexity: O(n^2) - Constructing the cumulative sum and checking subarrays is quadratic.
- Space Complexity: O(n) - We use a cumulative sum array that takes linear space.
3. Prefix Sum + HashMap
This optimized approach leverages a HashMap to track the number of times a particular cumulative sum has appeared.
Intuition:
While iterating through the array, we keep track of the cumulative sum. We use a HashMap to store the frequency of each cumulative sum we have encountered. For each new cumulative sum currentSum, we check if currentSum - k exists in the HashMap. If it does, it means there is a subarray ending at the current index with sum k.
Code:
- Time Complexity: O(n) - We iterate through the array once while maintaining and querying the HashMap in constant average time.
- Space Complexity: O(n) - The HashMap can potentially store all cumulative sums encountered.