
Problem Statement
In this problem, you are presented with an array of integers, nums
, and a single integer, k
. Your task is to determine the number of subarrays within nums
that sum up to k
. A "subarray" is defined as a contiguous, non-empty portion of the original array. Thus, each subarray represents a sequential subset of the elements from nums
.
Examples
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
Approach and Intuition
To solve the problem of finding the number of subarrays that sum up to k
, we can explore several approaches. Here's a step-by-step breakdown of a feasible method using a hashmap to track the cumulative sums:
Initialize a hashmap (or dictionary in Python) to store the cumulative sums encountered so far. The key will be the sum, and the value will be how frequently this sum appears.
Initialize the hashmap with the key
0
set to1
. This accounts for a subarray that might begin from the first element and sum tok
.Initialize a variable,
current_sum
, to zero. This will keep the cumulative total as we iterate through the list.Initialize a variable,
count
, to zero. This will count the number of times we find a subarray that sums tok
.Iterate through each element in
nums
. For each element:- Add it to
current_sum
. - Calculate the difference between the
current_sum
andk
. This difference tells us the sum we need to have seen before in thecurrent_sum
sequence to form a subarray totaling tok
at the current element. - If this difference exists in the hashmap, it means that there were some prior subarrays that sum to this difference. The number of such arrays gives the number of times a k-sum subarray ends at the current location.
- Increment the
count
by how many times the needed sum (difference calculated earlier) has been seen. - Update the hashmap with the new
current_sum
. Ifcurrent_sum
has already been seen, increment its value to indicate it's happened again; otherwise, add it to the hashmap.
- Add it to
This approach efficiently counts the required subarrays with the desired sum by leveraging the cumulative sum technique and hashmap storage. The key insight is recognizing that the condition current_sum - k
existing in our cumulative sum records indicates that a valid subarray (or subarrays) can be formed ending at the current index. This method provides a linear time complexity relative to the array's length, making it suitable for even larger datasets within the provided constraints.
Solutions
- Java
public class Solution {
public int countSubarraysWithSum(int[] array, int target) {
int total = 0, cumulativeSum = 0;
HashMap<Integer, Integer> prefixSums = new HashMap<>();
prefixSums.put(0, 1);
for (int j = 0; j < array.length; j++) {
cumulativeSum += array[j];
if (prefixSums.containsKey(cumulativeSum - target))
total += prefixSums.get(cumulativeSum - target);
prefixSums.put(cumulativeSum, prefixSums.getOrDefault(cumulativeSum, 0) + 1);
}
return total;
}
}
The provided Java solution calculates how many subarrays within an array have a sum equal to a specified target value. Follow the approach below to understand the implementation details.
- Initialize two integer variables:
total
to store the final count of subarrays andcumulativeSum
to store the sum of elements as you iterate through the array. - Create a
HashMap
namedprefixSums
to store the cumulative sum up to each index as the key and the number of times this cumulative sum has occurred as the value. Start by putting the key-value pair(0, 1)
in the map to handle cases where the subarray starts from index 0.
As you iterate through each element of the array:
- Add the current element to
cumulativeSum
. - Check if
(cumulativeSum - target)
exists in theprefixSums
map. If it does, the difference between the current cumulative sum and this key indicates a subarray sum that equals the target. Add the value ofprefixSums.get(cumulativeSum - target)
tototal
. - Update
prefixSums
for the currentcumulativeSum
. If it doesn't exist, add it with a default count of 0 and then increment by 1.
At the end of the loop, the total
variable contains the final count of subarrays whose sum equals the specified target. The use of a hashmap optimizes the search for the required sums, effectively reducing the computational overhead compared to a naive approach involving nested loops.
No comments yet.