Subarrays with sum K

Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.

Examples:

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.

Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.

Input: arr = [1, 3, 5], k = 0
Output: 0
Explaination: No subarray with 0 sum.

Constraints:

• 1 ≤ arr.size() ≤ 10⁵
• -10³ ≤ arr[i] ≤ 10³
• -10⁷ ≤ k ≤ 10⁷

Approach 01:

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

class Solution {
public:
    int countSubarrays(vector<int>& nums, int targetSum) {
        unordered_map<int, int> prefixSumFrequency;
        int currentPrefixSum = 0;
        int subarrayCount = 0;

        // Initialize the map with prefix sum 0 having frequency 1
        prefixSumFrequency[0] = 1;

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

            // Check if there exists a prefix sum such that currentPrefixSum - prefixSum = targetSum
            if (prefixSumFrequency.find(currentPrefixSum - targetSum) != prefixSumFrequency.end()) {
                subarrayCount += prefixSumFrequency[currentPrefixSum - targetSum];
            }

            // Update the frequency of the current prefix sum in the map
            ++prefixSumFrequency[currentPrefixSum];
        }

        return subarrayCount;
    }
};

from typing import List
from collections import defaultdict

class Solution:
    def countSubarrays(self, nums: List[int], targetSum: int) -> int:
        prefixSumFrequency = defaultdict(int)
        currentPrefixSum = 0
        subarrayCount = 0

        # Initialize the dictionary with prefix sum 0 having frequency 1
        prefixSumFrequency[0] = 1

        for num in nums:
            currentPrefixSum += num

            # Check if there exists a prefix sum such that currentPrefixSum - prefixSum = targetSum
            if currentPrefixSum - targetSum in prefixSumFrequency:
                subarrayCount += prefixSumFrequency[currentPrefixSum - targetSum]

            # Update the frequency of the current prefix sum in the dictionary
            prefixSumFrequency[currentPrefixSum] += 1

        return subarrayCount

Time Complexity:

• Single Iteration:
  • We iterate through the array once, performing a constant amount of work for each element.
  • The prefix sum calculation, map lookup, and insertion all take \( O(1) \) on average.
  • For \( n \) elements in the array, this contributes \( O(n) \) to the time complexity.
• Overall Time Complexity:

  \( O(n) \), where \( n \) is the size of the input array.

Space Complexity:

• Prefix Sum Map:
  • The map stores at most \( n + 1 \) entries (one for each prefix sum and the initial 0 prefix sum).
  • Each entry in the map requires constant space.
  • The space used by the map is \( O(n) \).
• Auxiliary Variables:
  • We use a few additional variables: \( currentPrefixSum \), \( subarrayCount \), and a loop counter, which all take \( O(1) \) space.
• Overall Space Complexity:

  \( O(n) \), dominated by the space used by the prefix sum map.