Subarray Sum Equals K medium

Problem Statement

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

Example 1:

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

Example 2:

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

Steps

1. Prefix Sum: We'll use a prefix sum approach. A prefix sum at index i is the sum of all elements from index 0 to i. We can efficiently calculate these sums.

2. Hash Map: We'll use a hash map (unordered_map in C++) to store the frequency of each prefix sum encountered so far. The key will be the prefix sum, and the value will be its count.

3. Iteration: We iterate through the nums array. For each element:

   • Calculate the current prefix sum.
   • Check if prefixSum - k exists as a key in the hash map. If it does, it means there's a subarray ending at the current index with a sum of k. We add its count to our result.
   • Update the frequency of the current prefixSum in the hash map.

4. Handle k=0: If k is 0, we must handle the case where a subarray with sum 0 exists separately since prefixSum -k would lead to division by zero.

Explanation

The core idea is that if the prefix sum at index i is prefixSum_i and the prefix sum at index j (where j < i) is prefixSum_j, then the sum of the subarray from index j+1 to i is prefixSum_i - prefixSum_j. If we want this sum to be equal to k, then prefixSum_i - prefixSum_j = k, which means prefixSum_i - k = prefixSum_j. Therefore, we check if prefixSum_i - k exists in our hash map. The number of times it exists represents the number of subarrays ending at index i with a sum of k.

Code

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> prefixSumCount; //Using long long to avoid overflow
    prefixSumCount[0] = 1; //Important: Initialize for subarrays starting at index 0
    long long prefixSum = 0;
    int count = 0;

    for (int num : nums) {
        prefixSum += num;
        if (prefixSumCount.count(prefixSum - k)) {
            count += prefixSumCount[prefixSum - k];
        }
        prefixSumCount[prefixSum]++;
    }

    return count;
}

int main() {
    vector<int> nums1 = {1, 1, 1};
    int k1 = 2;
    cout << "Example 1: " << subarraySum(nums1, k1) << endl; // Output: 2

    vector<int> nums2 = {1, 2, 3};
    int k2 = 3;
    cout << "Example 2: " << subarraySum(nums2, k2) << endl; // Output: 2

    vector<int> nums3 = {-1,-1,1};
    int k3 = 0;
    cout << "Example 3: " << subarraySum(nums3, k3) << endl; // Output: 1

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once. Hash map operations (insertion and lookup) are on average O(1).
• Space Complexity: O(n) in the worst case, as the hash map could store up to n different prefix sums. In the best case it could be O(1) (if there are very few unique prefix sums).