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 represents the sum of all elements from index 0 up to i.
2. Hash Map: We'll use a hash map (dictionary in Python) to store the frequency of each prefix sum encountered. The key will be the prefix sum, and the value will be its count.
3. Initialization: We start with a prefix sum of 0 and its count as 1 (an empty subarray has a sum of 0).
4. Iteration: We iterate through the nums array. For each element:
   • We update the current prefix sum.
   • We 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.
   • We update the count of the current prefixSum in the hash map.

Explanation

The core idea is that if the prefix sum at index i is prefixSum, and prefixSum - k exists, it implies there was a previous prefix sum (prefixSum - k) such that the sum of elements between that previous prefix sum and the current prefix sum is exactly k.

For instance, consider nums = [1, 2, 3] and k = 3.

• Initially, prefixSum = 0, count(0) = 1.
• nums[0] = 1: prefixSum = 1, count(1) = 1.
• nums[1] = 2: prefixSum = 3, prefixSum - k = 0, count(0) = 1, so we add 1 to the result. count(3) = 1.
• nums[2] = 3: prefixSum = 6, prefixSum - k = 3, count(3) = 1, so we add 1 to the result. count(6) = 1.

The result is 2.

Code

def subarraySum(nums, k):
    """
    Finds the total number of continuous subarrays whose sum equals k.

    Args:
        nums: A list of integers.
        k: The target sum.

    Returns:
        The total number of subarrays with sum k.
    """
    prefix_sum = 0
    count = 0
    prefix_sum_counts = {0: 1}  # Initialize with prefix sum 0 having count 1

    for num in nums:
        prefix_sum += num
        if prefix_sum - k in prefix_sum_counts:
            count += prefix_sum_counts[prefix_sum - k]
        prefix_sum_counts[prefix_sum] = prefix_sum_counts.get(prefix_sum, 0) + 1

    return count

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Hash map lookups and insertions are on average O(1).
• Space Complexity: O(n) in the worst case, as the hash map could potentially store all prefix sums. In the best case, it's O(1) if there are very few unique prefix sums.