Problem Explanation

We are given an array of integers and a target integer value k. Our task is to find the total number of continuous subarrays whose sum is equal to k. A subarray must be contiguous elements and not necessarily the entire original array.

Let's consider an example:

Example:

1
2
3Input: nums = [1,1,1], k = 2

In this example, the subarrays with sum equal to k=2 are: [1, 1] and [1, 1]. Hence, the output is 2.

Approach

The approach used to solve this problem involves using prefix sums and hash map data structure. The key idea is to maintain a count of prefix sums along with their frequencies, and for each prefix sum encountered, we check if prefix sum - k is present in our hash map or not. This is because if prefix sum - k is present in our hash map, it means that there is a continuous subarray whose sum equals to k.

Step By Step Algorithm

1. Initialize the ans variable to store the number of subarrays, and prefix variable to store the current prefix sum.
2. Initialize a hash map count to store the prefix sums and their respective counts. Initialize it with 0:1, meaning sum 0 has 1 occurrence.
3. For each num in nums array:
   • Add num to prefix.
   • Calculate the target by subtracting k from prefix.
   • If target is present in count, add the frequency of target to ans.
   • Increment the count of prefix in count.
4. Finally, return ans.

Java Solution

1
2java
3class Solution {
4    public int subarraySum(int[] nums, int k) {
5        int count = 0, sum = 0;
6        HashMap<Integer, Integer> hmap = new HashMap<>();
7        hmap.put(0, 1);
8        for (int i = 0; i < nums.length; i++) {
9            sum += nums[i];
10            if (hmap.containsKey(sum - k))
11                count += hmap.get(sum - k);
12            hmap.put(sum, hmap.getOrDefault(sum, 0) + 1);
13        }
14        return count;
15    }
16}

Python Solution

1
2python
3class Solution:
4    def subarraySum(self, nums: List[int], k: int) -> int:
5        count = collections.Counter()
6        count[0] = 1
7        ans = sum = 0
8        for x in nums:
9            sum += x
10            ans += count[sum-k]
11            count[sum] += 1
12        return ans  

JavaScript Solution

1
2javascript
3var subarraySum = function(nums, k) {
4    let count = 0, sum = 0;
5    let map = new Map();
6    map.set(0, 1);
7    for(let i = 0; i < nums.length; i++) {
8        sum += nums[i];
9        if(map.has(sum - k))
10            count += map.get(sum - k);
11        map.set(sum, (map.get(sum) || 0) + 1);
12    }
13    return count;
14};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int subarraySum(vector<int>& nums, int k) {
6        int count = 0;
7        int sum = 0;
8        unordered_map<int, int> sums {{0, 1}};
9        for (int num : nums) {
10            sum += num;
11            if (sums.count(sum - k)) count += sums[sum - k];
12            ++sums[sum];
13        }
14        return count;
15    }
16};

C# Solution

1
2csharp
3public class Solution {
4    public int SubarraySum(int[] nums, int k) {
5        var dict = new Dictionary<int, int>() { {0, 1}};
6        int sum = 0, count = 0;
7        for (int i = 0; i < nums.Length; i++) {
8            sum += nums[i];
9            if (dict.ContainsKey(sum - k)) count += dict[sum - k];
10            if (dict.ContainsKey(sum)) dict[sum]++;
11            else dict.Add(sum, 1);
12        }
13        return count;
14    }
15}

Here, in all the solutions, we use a hash map to remember the prefix sum and its frequency, and for each number in the array, we add it to the prefix sum and then check if prefix sum - k is present in the hash map or not. If it is present, we increment the count with the frequency of prefix sum - k from the hash map.## Explanation

These solutions iterate over all elements in the input array, maintaining the sum of the numbers processed so far and a count of the frequency of all the prefix sums encountered so far in a hash map. For each number in the array, the corresponding sum is checked in the map for its frequency, and the result is updated by adding the frequency, if found.

In the Python solution, the collections library has been used, specifically the Counter class, to count the frequency of each prefix sum with a default value of 0. The JavaScript, Java, and C# solutions use respective hash map classes with their in-built functions to handle default values.

The method .getOrDefault() in Java and C# is used to avoid KeyError exceptions that might occur while accessing keys that are not in the hash map. It provides a default value when the key is not present in the hash map. The JavaScript solution uses a short-circuit OR (||) to provide a default value when the key is not present in the Map object. Python’s Counter object also has a default value of zero, so there is no need to check if the key exists in the dictionary.

The key point to understand is that the prefix sum up to an index i is computed and then k is subtracted from it. The math behind this is the fact that any subsequence sum can be computed by subtracting two prefix sums. Hence, if the result of this subtraction (suppose it is pSum) is already present in the map, it means that there is a subsequence sum equal to k.

This very fact is used to count the number of subsequence sums equal to k.

Time Complexity

In the worst case, all these solutions have a time complexity of O(n), where n is the length of the input array, as there is a single loop traversing each element in the array once.

Space Complexity

The worst-case space complexity is also O(n) due to the additional data structure (hash map) used to store prefix sums and their frequencies. The space complexity could be less than n if fewer than n distinct prefix sums are found.