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

Explanation: The subarrays are [1,1] and [1,1].

Example 2:

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

Explanation: The subarrays are [1,2] and [3].

Steps and Explanation

This problem can be efficiently solved using a hash map (dictionary in C#) to store the cumulative sum and its frequency. We iterate through the array, calculating the cumulative sum at each step. For each cumulative sum, we check if a previous cumulative sum exists such that their difference is equal to k. If it does, it means we've found a subarray with a sum of k.

1. Initialization: Create a dictionary sumCount to store the cumulative sum as the key and its frequency as the value. Initialize the cumulative sum currentSum to 0 and the count of subarrays count to 0. Add an entry (0, 1) to sumCount to handle cases where the subarray starts from the beginning and sums to k.

2. Iteration: Iterate through the nums array.

3. Cumulative Sum Update: For each element num, update currentSum by adding num.

4. Check for Subarray: Check if currentSum - k exists as a key in sumCount. If it does, it means there's a previous cumulative sum whose difference with the current sum is k. Add the frequency of that previous cumulative sum to count.

5. Update Frequency: Update the frequency of currentSum in sumCount. If it's not present, add it with a frequency of 1; otherwise, increment its frequency.

6. Return Count: After iterating through the entire array, return count.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        Dictionary<int, int> sumCount = new Dictionary<int, int>();
        sumCount.Add(0, 1); // Handle cases where subarray starts from beginning

        int currentSum = 0;
        int count = 0;

        foreach (int num in nums) {
            currentSum += num;

            if (sumCount.ContainsKey(currentSum - k)) {
                count += sumCount[currentSum - k];
            }

            if (sumCount.ContainsKey(currentSum)) {
                sumCount[currentSum]++;
            } else {
                sumCount.Add(currentSum, 1);
            }
        }

        return count;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Dictionary lookups and insertions are on average O(1).

• Space Complexity: O(n) in the worst case, as the sumCount dictionary could potentially store all cumulative sums. In the best case, it could be O(1) if there are very few distinct cumulative sums.