Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals tok.
A subarray is a contiguous non-empty sequence of elements within an array.
Problem Statement
The problem is to find the total number of subarrays in an array of integers whose sum equals to a given integer k. The array may contain negative
integers and duplicates, and the subarrays must be contiguous and non-empty. The output should be a single integer representing the total number
of subarrays that satisfy the condition.
Examples
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Clarifying Questions
Can the input array contain negative integers?
Is the subarray required to be non-empty?
Are there any constraints on the size of the input array and the value of k?
Are we allowed to use additional data structures or do we need to solve this problem in-place?
Can the input array contain duplicates? If yes, do we need to consider all possible combinations of subarrays with the same sum?
Solutions
There are several approaches to solving this problem, including:
Approach 1: Brute Force
This involves using two nested loops to iterate over all possible subarrays of the input array and checking if their sum equals k. This approach
has a time complexity of O(n^2), where n is the size of the input array.
Algorithm:
Initialize a count variable to zero.
Iterate over all possible subarrays of the input array using two nested loops.
For each subarray, compute the sum of its elements.
If the sum equals k, increment the count variable.
Return the count variable.
public static int SubarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
for (int i = 0; i < nums.Length; i++) {
int sum = 0;
for (int j = i; j < nums.Length; j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count; // Return the count variable
}
def subarray_sum(nums: List[int], k: int) -> int:
count = 0 # Initialize count variable to 0
for i in range(len(nums)):
sum = 0
for j in range(i, len(nums)):
sum += nums[j]
if sum == k:
count += 1
return count # Return the count variable
public static int subarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count; // Return the count variable
}
int subarraySum(vector<int>& nums, int k) {
int count = 0; // Initialize count variable to 0
for (int i = 0; i < nums.size(); i++) {
int sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count; // Return the count variable
}
Note that in all implementations, we first initialize the count variable to zero, then use two nested loops to iterate over all possible subarrays
of the input array, computing their sum and checking if it equals k. If it does, we increment the count variable. Finally, we return the count
variable as the output.
Time complexity: We use two nested loops to iterate through all possible subarrays of the given array. The time complexity of
this approach is O(n^2), where n is the length of the input array.
Space complexity: The space complexity is O(1) since we are not using any extra space other than the input array.
Approach 2: Hash Map
This approach involves using a hash map to store the cumulative sum of the elements in the array up to a certain index. We then iterate over the
array and for each index, we check if the difference between the cumulative sum up to that index and k exists in the hash map. If it does, we
increment the count of subarrays. This approach has a time complexity of O(n), where n is the size of the input array.
Algorithm:
Initialize a count variable to zero.
Initialize a hash map with an initial key-value pair of (0,1) to handle the case where a subarray starting from index 0 has sum k.
Initialize a variable 'sum' to 0.
Iterate over the input array from left to right.
For each element, add it to 'sum'.
Compute the difference between 'sum' and k.
If the difference exists in the hash map, add the value associated with that key to the count variable.
If the difference does not exist in the hash map, add a new key-value pair of (sum,1) to the hash map.
Return the count variable.
public static int SubarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
int sum = 0;
Dictionary<int, int> map = new Dictionary<int, int>();
map.Add(0, 1); // Add an initial key-value pair to the map
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
// If the map already contains the complement, increment the count by the value of the complement in the map
if (map.ContainsKey(sum - k)) {
count += map[sum - k];
}
// Add the current sum to the map
if (map.ContainsKey(sum)) {
map[sum]++;
}
else {
map.Add(sum, 1);
}
}
return count; // Return the count variable
}
def subarray_sum(nums: List[int], k: int) -> int:
count = 0 # Initialize count variable to 0
sum = 0
map = {0: 1} # Add an initial key-value pair to the map
for i in range(len(nums)):
sum += nums[i]
# If the map already contains the complement, increment the count by the value of the complement in the map
if sum - k in map:
count += map[sum - k]
# Add the current sum to the map
if sum in map:
map[sum] += 1
else:
map[sum] = 1
return count # Return the count variable
public static int subarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
int sum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // Add an initial key-value pair to the map
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// If the map already contains the complement, increment the count by the value of the complement in the map
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
// Add the current sum to the map
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count; // Return the count variable
}
int subarraySum(vector<int>& nums, int k) {
int count = 0; // Initialize count variable to 0
int sum = 0;
unordered_map<int, int> map;
map[0] = 1; // Add an initial key-value pair to the map
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
// If the map already contains the complement, increment the count by the value of the complement in the map
if (map.count(sum - k)) {
count += map[sum - k];
}
// Add the current sum to the map
map[sum]++;
}
return count; // Return the count variable
}
Time complexity: The time complexity of this approach is O(n), where n is the length of the input array, since we traverse the
input array only once.
Space complexity: The space complexity is also O(n) since in the worst case scenario, all elements of the input array can be
distinct and hence the hash map would need to store n distinct entries.
Approach 3: Prefix Sum
This approach is similar to the hash map approach but uses an array to store the cumulative sum instead of a hash map. We then iterate over the
array and for each index, we check if the difference between the cumulative sum up to that index and k exists in the prefix sum array. If it does,
we increment the count of subarrays. This approach also has a time complexity of O(n), where n is the size of the input array.
Algorithm:
Initialize a count variable to zero.
Initialize a prefix sum array of size n+1, where n is the size of the input array, with an initial value of 0 at index 0.
Initialize a variable 'sum' to 0.
Iterate over the input array from left to right.
For each element, add it to 'sum' and store the value in the prefix sum array at the current index + 1.
Compute the difference between the current prefix sum and k.
If the difference exists in the prefix sum array up to the current index, add the number of occurrences to the count variable.
Increment the value of the prefix sum array at the current index + 1.
Return the count variable.
public static int SubarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
int[] prefixSum = new int[nums.Length + 1]; // Initialize prefix sum array of size nums.Length + 1
prefixSum[0] = 0; // Set the first element of the prefix sum array to 0
// Calculate the prefix sum of nums array and store it in prefixSum array
for (int i = 1; i <= nums.Length; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Calculate the subarray sum by subtracting two prefix sums
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j <= nums.Length; j++) {
if (prefixSum[j] - prefixSum[i] == k) { // If the subarray sum equals k, increment count
count++;
}
}
}
return count; // Return the count variable
}
def subarray_sum(nums: List[int], k: int) -> int:
count = 0 # Initialize count variable to 0
prefix_sum = [0] * (len(nums) + 1) # Initialize prefix sum array of size len(nums) + 1
prefix_sum[0] = 0 # Set the first element of the prefix sum array to 0
# Calculate the prefix sum of nums list and store it in prefix_sum array
for i in range(1, len(nums) + 1):
prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
# Calculate the subarray sum by subtracting two prefix sums
for i in range(len(nums)):
for j in range(i + 1, len(nums) + 1):
if prefix_sum[j] - prefix_sum[i] == k: # If the subarray sum equals k, increment count
count += 1
return count # Return the count variable
public static int subarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable to 0
int[] prefixSum = new int[nums.length + 1]; // Initialize prefix sum array of size nums.length + 1
prefixSum[0] = 0; // Set the first element of the prefix sum array to 0
// Calculate the prefix sum of nums array and store it in prefixSum array
for (int i = 1; i <= nums.length; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Calculate the subarray sum by subtracting two prefix sums
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j <= nums.length; j++) {
if (prefixSum[j] - prefixSum[i] == k) { // If the subarray sum equals k, increment count
count++;
}
}
}
return count; // Return the count variable
}
int subarraySum(vector<int>& nums, int k) {
int count = 0; // Initialize
vector<int> prefixSum(nums.size() + 1, 0); // Initialize prefix sum vector of size nums.size() + 1
// Calculate the prefix sum of nums vector and store it in prefixSum vector
for (int i = 1; i <= nums.size(); i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Calculate the subarray sum by subtracting two prefix sums
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j <= nums.size(); j++) {
if (prefixSum[j] - prefixSum[i] == k) { // If the subarray sum equals k, increment count
count++;
}
}
}
return count; // Return the count variable
}
Time complexity: The time complexity of this approach is O(n), where n is the length of the input array, since we traverse the
input array only twice.
Space complexity: The space complexity is O(n) since we use an extra prefix sum array of length n.
Approach 4: Two Pointers
This approach involves using two pointers to maintain a sliding window of the subarray.
We initialize two pointers, left and right, at the start of the array.
We then move the right pointer forward until the sum of the subarray is greater than or equal to k. At this point, we increment the count of
subarrays and move the left pointer forward until the sum of the subarray is less than k.
We repeat this process until we reach the end of the array.
This approach also has a time complexity of O(n^2), where n is the size of the input array.
Algorithm:
Initialize a count variable to zero.
Initialize two pointers, left and right, to the start of the input array.
Initialize a variable 'sum' to 0.
Iterate over the input array from left to right using the right pointer.
For each element, add it to 'sum'.
While the sum is greater than k, move the left pointer forward and subtract the corresponding element from 'sum'.
If the sum equals k, increment the count variable.
Repeat steps d-g until the right pointer reaches the end of the input array.
Return the count variable.
public int SubarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable
int left = 0; // Initialize left pointer
int right = 0; // Initialize right pointer
int sum = 0; // Initialize sum variable
while (right < nums.Length) { // Loop through nums array
sum += nums[right]; // Add current element to sum
right++; // Increment right pointer
while (left < right && sum > k) { // If sum is greater than k, move the left pointer and subtract the element
sum -= nums[left];
left++;
}
if (sum == k) { // If sum equals k, increment count
count++;
}
}
return count; // Return the count variable
}
def subarraySum(nums: List[int], k: int) -> int:
count = 0 # Initialize count variable
left = 0 # Initialize left pointer
right = 0 # Initialize right pointer
summ = 0 # Initialize sum variable
while right < len(nums): # Loop through nums list
summ += nums[right] # Add current element to sum
right += 1 # Increment right pointer
while left < right and summ > k: # If sum is greater than k, move the left pointer and subtract the element
summ -= nums[left]
left += 1
if summ == k: # If sum equals k, increment count
count += 1
return count # Return the count variable
public int subarraySum(int[] nums, int k) {
int count = 0; // Initialize count variable
int left = 0; // Initialize left pointer
int right = 0; // Initialize right pointer
int sum = 0; // Initialize sum variable
while (right < nums.length) { // Loop through nums array
sum += nums[right]; // Add current element to sum
right++; // Increment right pointer
while (left < right && sum > k) { // If sum is greater than k, move the left pointer and subtract the element
sum -= nums[left];
left++;
}
if (sum == k) { // If sum equals k, increment count
count++;
}
}
return count; // Return the count variable
}
int subarraySum(vectorvector<int>& nums, int k) {
int count = 0; // Initialize count variable
int left = 0; // Initialize left pointer
int right = 0; // Initialize right pointer
int sum = 0; // Initialize sum variable
while (right < nums.size()) { // Loop through nums vector
sum += nums[right]; // Add current element to sum
right++; // Increment right pointer
while (left < right && sum > k) { // If sum is greater than k, move the left pointer and subtract the element
sum -= nums[left];
left++;
}
if (sum == k) { // If sum equals k, increment count
count++;
}
}
return count; // Return the count variable
}
Time complexity:
The time complexity of this code is O(n^2), where n is the length of the input array nums.
The outer while loop iterates through the array once, so it has a time complexity of O(n). However, the inner while loop may also iterate through
the array for each element in the outer loop. In the worst case, where all elements in the array have a sum equal to k, the inner loop will
iterate through the array for each element in the outer loop, resulting in a total of O(n^2) iterations.
Therefore, the overall time complexity is O(n^2).
Space complexity: The space complexity is O(1) since we are not using any extra space other than some constant number of
variables.
