# Subarray Sum Equals K

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.

## 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

1. Can the input array contain negative integers?
2. Is the subarray required to be non-empty?
3. Are there any constraints on the size of the input array and the value of k?
4. Are we allowed to use additional data structures or do we need to solve this problem in-place?
5. 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:

1. Initialize a count variable to zero.
2. Iterate over all possible subarrays of the input array using two nested loops.
3. For each subarray, compute the sum of its elements.
4. If the sum equals k, increment the count variable.
5. 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:

1. Initialize a count variable to zero.
2. 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.
3. Initialize a variable 'sum' to 0.
4. Iterate over the input array from left to right.
5. For each element, add it to 'sum'.
6. Compute the difference between 'sum' and k.
7. If the difference exists in the hash map, add the value associated with that key to the count variable.
8. If the difference does not exist in the hash map, add a new key-value pair of (sum,1) to the hash map.
9. 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:

1. Initialize a count variable to zero.
2. 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.
3. Initialize a variable 'sum' to 0.
4. Iterate over the input array from left to right.
5. For each element, add it to 'sum' and store the value in the prefix sum array at the current index + 1.
6. Compute the difference between the current prefix sum and k.
7. If the difference exists in the prefix sum array up to the current index, add the number of occurrences to the count variable.
8. Increment the value of the prefix sum array at the current index + 1.
9. 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:

1. Initialize a count variable to zero.
2. Initialize two pointers, left and right, to the start of the input array.
3. Initialize a variable 'sum' to 0.
4. Iterate over the input array from left to right using the right pointer.
5. For each element, add it to 'sum'.
6. While the sum is greater than k, move the left pointer forward and subtract the corresponding element from 'sum'.
7. If the sum equals k, increment the count variable.
8. Repeat steps d-g until the right pointer reaches the end of the input array.
9. 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.

Share: