Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Examples

Example 1:

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

Explanation: In the given array [1, 1, 1], there are two subarrays
that sum up to 2. 
[1, 1] and [1, 1]. Hence we got 2.

Example 2:

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

Explanation: In the given array [1, 2, 3], there are two subarrays
that sum up to 3: [1, 2] and [3]. Hence we got 2 as the output.

Example 3:

Input: nums = [3, 1, 2, 4], k = 6
Output: 2

Explanantion: In the given array [3, 1, 2, 4], there are two subarrays
whose sum is 6.
[3, 1, 2] and [2, 4], Hence we got output 2.

Different Approaches

1️⃣ Brute Force Approach

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size();
        // Number of subarrays
        int cnt = 0;

        // starting index i
        for (int i = 0; i < n; i++) {
            // ending index j
            for (int j = i; j < n; j++) {

                // calculate the sum of subarray [i...j]
                int sum = 0;
                for (int K = i; K <= j; K++)
                    sum += nums[K];

                // Increase the count if sum == k:
                if (sum == k)
                    cnt++;
            }
        }
        return cnt;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 1, 2, 4};
    int k = 6;
    // Function call to find the result
    int cnt = solution.subarraySum(nums, k);
    cout << "The number of subarrays is: " << cnt << "\n";
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n^3), where n is the size of the array. We are using three nested loops. Although all loops are not running exactly n times. However will be approximately O(n^3).
• Space Complexity: O(1)

2️⃣ Better Approach

Intuition:

If we carefully observe, we can notice that to get the sum of the current subarray, the only need is to add the current element (i.e., arr[j]) to the sum of the previous subarray, arr[i…j-1]. Assume the previous subarray is arr[i…j-1] and the current subarray is arr[i…j]. The sum of arr[i…j] can be calculated as:

Sum of arr[i…j] = (sum of arr[i…j-1]) + arr[j]

This way, eliminate the third loop, and while moving the j pointer, continuously calculate the sum.

Approach:

1. First, run a loop (i) that will select every possible starting index of the subarray. The starting indices can range from index 0 to index n-1 (where n is the array size).
2. Inside this loop, run another loop (j) that will signify the ending index as well as the current element of the subarray. For every subarray starting from index i, the possible ending indices can range from index i to n-1 (where n is the array size).
3. Within the j loop, add the current element to the sum of the previous subarray, i.e., sum = sum + arr[j].
4. After calculating the sum, check if the sum is equal to the given k. If it is, increment the count.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size(); 
        // Number of subarrays
        int count = 0;

        // starting index
        for (int startIndex = 0; startIndex < n; startIndex++) { 
            int currentSum = 0;
            // ending index
            for (int endIndex = startIndex; endIndex < n; endIndex++) { 
                // calculate the sum of subarray [startIndex...endIndex]
                // sum of [startIndex..endIndex-1] + nums[endIndex]
                currentSum += nums[endIndex];

                // Increase the count if currentSum == k:
                if (currentSum == k)
                    count++;
            }
        }
        return count;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {3, 1, 2, 4};
    int k = 6;
    // Function call to find the result
    int count = solution.subarraySum(nums, k);
    cout << "The number of subarrays is: " << count << "\n";
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n^2), where n is the number of elements in the array.
  • We are using two nested loops here, each running approximately n times.
• Space Complexity: O(1)

3️⃣ Optimal Approach

Intuition:

In this approach, we will use the concept of prefix sums to solve the problem. The prefix sum of a subarray ending at index i is simply the sum of all the elements up to that index.

Approach:

1. First, declare a map to store the prefix sums and their counts. Initially, set the value of 0 to 1 in the map to handle cases where a subarray equals the target sum k.
2. Now, run a loop from index 0 to n-1 (where n is the size of the array). For each index i, we will add the current element arr[i] to the prefix sum, calculate the required prefix sum x-k, add the occurrence of the prefix sum x-k (i.e., map[x-k]) to our answer, and store the current prefix sum in the map, increasing its count by 1.
3. Setting the initial value of 0 to 1 in the map is crucial for handling edge cases. For example, if the array is [3, -3, 1, 1, 1] and k is 3, at index 0, the prefix sum is 3, which equals k. The prefix sum of the part to be removed should be x-k = 3-3 = 0.
4. Without setting the value of 0 beforehand, the map would return 0 for the key 0, meaning we wouldn't count the subarray starting from the beginning correctly. By setting the initial value of 0 to 1, ensure that such subarrays are correctly counted from the start. This adjustment ensures that any subarray starting at the beginning of the array and equaling k is not overlooked.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int countSubarraysWithSum(vector<int>& nums, int target) {
    unordered_map<int, int> prefixSumCount; // Stores prefix sums and their frequencies
    prefixSumCount[0] = 1; // Base case
    int prefixSum = 0, count = 0;

    for (int num : nums) {
        prefixSum += num;

        // Check if the required prefix sum exists
        if (prefixSumCount.find(prefixSum - target) != prefixSumCount.end()) {
            count += prefixSumCount[prefixSum - target];
        }

        // Update the prefix sum frequency
        prefixSumCount[prefixSum]++;
    }

    return count;
}

int main() {
    vector<int> nums = {1, 1, 1};
    int target = 2;
    cout << "Count of subarrays with sum " << target << ": " << countSubarraysWithSum(nums, target) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) or O(NxlogN) depending on the map data structure used, where N is the size of the array. For example, if we use an unordered_map in C++, the time complexity will be O(N), but if we use a map, the time complexity will be O(NxlogN). The minimum complexity is O(N) as we are using a single loop to traverse the array.
• Space Complexity: O(N) as we are using a map data structure.