In the “Subarray Sum Equals K” problem, you are given an array of integers and a target integer, k. The goal is to find the number of contiguous subarrays within the array that sum up to k. Think of it as searching for specific sections in the array where adding up the numbers gives you exactly the target k.
Brute-Force Approach
A brute-force solution tries all possible subarrays to see if any of them add up to k. This approach is simple to understand but can be slow, especially for large arrays, because it looks at every possible subarray.
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
}In this solution:
1. We iterate through the array with two nested loops.
2. For each starting point (start), we calculate the sum of each subarray ending at end.
3. If a subarray’s sum equals k, we increment the count.
This approach checks every possible subarray, making it straightforward but slow, especially for larger inputs.
Optimal Approach with HashMap and Cumulative Sum
Algorithm Choice and Data Structure: The optimal solution uses a cumulative sum pattern with a HashMap. This approach reduces the need to compute each subarray sum repeatedly by storing previously calculated sums in a HashMap, which helps us quickly check if any previous cumulative sum creates the difference we need to find k.
• Why This Algorithm Fits: The cumulative sum pattern is particularly useful here because each element’s cumulative sum helps determine the sum of subarrays ending at the current position. By using a HashMap to store cumulative sums and their occurrences, we can identify subarrays with the required sum efficiently.
• Pattern Recognition: When a problem involves finding subarrays with a specific sum, the cumulative sum combined with a HashMap often provides an efficient solution by leveraging the mathematical relationship between sums at different indices.
• Why It’s Better than Brute Force: The brute-force method recalculates subarray sums multiple times, while the cumulative sum approach only requires a single pass and constant-time lookups, reducing time complexity.
Steps of the Algorithm
1. Initialize a HashMap to store cumulative sums and their frequencies.
2. Loop through the array, updating the cumulative sum.
3. Check if the cumulative sum minus k exists in the map, indicating a subarray that sums to k.
4. Add the cumulative sum to the map, updating its frequency.
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, cumulativeSum = 0;
HashMap<Integer, Integer> sumFrequency = new HashMap<>();
sumFrequency.put(0, 1); // Initialize for subarrays starting from index 0
for (int num : nums) {
cumulativeSum += num;
if (sumFrequency.containsKey(cumulativeSum - k)) {
count += sumFrequency.get(cumulativeSum - k);
}
sumFrequency.put(cumulativeSum, sumFrequency.getOrDefault(cumulativeSum, 0) + 1);
}
return count;
}
}Line-By-Line Detailed Explanation
- Initializing Variables
int count = 0, cumulativeSum = 0;- count will store the total number of subarrays that sum to j
- cumulativeSum will keep track of the running sum of elements as we go thru the array, which allows us to check if a subarray ending at the current elements adds up to k.
2. Initializing the HashMap
HashMap<Integer, Integer> sumFrequency = new HashMap<>();
sumFrequency.put(0, 1); // Initialize for subarrays starting from index 0- sumFrequency will store cumulative sums as keys and their counts as values.
- sumFrequency.put(0, 1); initializes the map with the cumulative sum 0 having a count of 1. This is a special setup step to handle subarrays that start from the beginning of the array and sum to k.
- The HashMap lets us check if any previous cumulative sum, when subtracted from the current cumulative sum, gives us k. Initializing it with 0 ensures that we handle subarrays starting from the beginning of the array correctly.
3. Looping Through Each Number in the Array
for (int num : nums) {- We start a loop over each number in the array. This loop will allow us to build up our cumulative sum and check subarrays ending at each position.
4. Updating the Cumulative Sum
cumulativeSum += num;- We add the current num to cumulativeSum, which gives us the sum of all elements up to this point.
- cumulativeSum is crucial because it represents the total sum from the start up to the current position. This running total helps us check if there’s a previous cumulative sum that, when subtracted, would give a subarray sum of k.
5. Checking for Previous Cumulative Sums
if (sumFrequency.containsKey(cumulativeSum - k)) {
count += sumFrequency.get(cumulativeSum - k);
}- cumulativeSum – k gives the difference between our current cumulative sum and k. This difference represents a previous cumulative sum where a subarray from that point to the current point sums to k.
- If this difference exists in sumFrequency, we increment count by the number of times that difference has been seen (using sumFrequency.get(cumulativeSum – k)).
- Why Does This Exist? This step checks if a previous cumulative sum allows a subarray ending at the current element to sum to k. Each match found in sumFrequency represents a subarray, so we add to count the number of such subarrays.
6. Updating the HashMap with the Current Cumulative Sum
sumFrequency.put(cumulativeSum, sumFrequency.getOrDefault(cumulativeSum, 0) + 1);- Adding current cumulative sum to the map allows us to track it for any future subarrays. If there’s a later cumulative sum that results in the difference cumulativeSum – k, we’ll be able to count the number of subarrays summing to k.
Why This Code Works
In summary, this solution leverages cumulative sums with a HashMap for efficient lookup, achieving a much lower time complexity (O(n)) compared to the brute-force approach (O(n^2)). This method is especially efficient for problems involving sums of subarrays due to its single-pass computation and reduced space complexity.
