Solution 1: Using Hashmap

Intuition:

To solve this problem efficiently, we can use a hashmap to keep track of the prefix sum of the subarrays encountered so far and their frequencies. As we traverse the array, we continuously update the prefix sum and check if prefix_sum - k exists in the hashmap. If it does, it means that there is a subarray whose sum equals k. We increment our count by the frequency of prefix_sum - k in the hashmap.

Solution:

from typing import List

def subarray_sum(nums: List[int], k: int) -> int:
    # Initialize variables
    count = 0
    prefix_sum = 0
    sum_freq = {0: 1}  # A hashmap to store the frequency of prefix sums
    
    # Traverse the array
    for num in nums:
        prefix_sum += num  # Calculate prefix sum
        if prefix_sum - k in sum_freq:
            count += sum_freq[prefix_sum - k]  # Increment count if prefix_sum - k exists in hashmap
        sum_freq[prefix_sum] = sum_freq.get(prefix_sum, 0) + 1  # Update sum frequency hashmap
    print(sum_freq)
    return count

# Test cases
result = subarray_sum([1, 1, 1], 2)
print(result)  # Output should be 2

result = subarray_sum([1, 2, 3], 3)
print(result)  # Output should be 2

result = subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7)
print(result)  # Output should be 4

result = subarray_sum([], 0)
print(result)  # Output should be 0

result = subarray_sum([0], 0)
print(result)  # Output should be 1

result = subarray_sum([0], 1)
print(result)  # Output should be 0

result = subarray_sum([0, 2, 3, 4], 1)
print(result)  # Output should be 0

Time Complexity:

  • The algorithm traverses the array once, which takes O(n) time, where n is the length of the input array..
  • Within the loop, constant time operations are performed to update the prefix sum and check for existence in the hashmap.
  • Therefore, the overall time complexity is O(n).

Space Complexity:

  • We use a hashmap to store the frequencies of prefix sums encountered, which can have at most n elements where n is the length of the input array.
  • Therefore, the space complexity is O(n).

Solution 2: Without Hashmap

Intuition:

There is another solution that utilizes a prefix sum array. We can precompute the prefix sums of all subarrays and then iterate through the array, checking for subarrays with the desired sum. This approach requires two nested loops: one to iterate through each starting index of the subarray and another to iterate through each ending index.

Solution:

from typing import List

from typing import List

def subarray_sum(nums: List[int], k: int) -> int:
    count = 0
    prefix_sums = [0] * (len(nums) + 1)
    
    # Compute prefix sums
    for i in range(1, len(prefix_sums)):
        prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
    
    # Iterate through all subarrays
    for i in range(len(nums)):
        for j in range(i + 1, len(nums) + 1):
            if prefix_sums[j] - prefix_sums[i] == k:
                count += 1
    
    return count

# Test cases
result = subarray_sum([1, 1, 1], 2)
print(result)  # Output should be 2

result = subarray_sum([1, 2, 3], 3)
print(result)  # Output should be 2

result = subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7)
print(result)  # Output should be 4

result = subarray_sum([], 0)
print(result)  # Output should be 0

result = subarray_sum([0], 0)
print(result)  # Output should be 1

result = subarray_sum([0], 1)
print(result)  # Output should be 0

result = subarray_sum([0, 2, 3, 4], 1)
print(result)  # Output should be 0

Time Complexity:

  • Computing prefix sums requires traversing the array once, taking O(n) time.
  • The nested loops iterate through each subarray, taking O(n^2) time in the worst case.
  • Therefore, the overall time complexity is O(n^2).

Space Complexity:

  • We use an additional prefix sum array of length n+1, taking O(n) space.
  • Therefore, the space complexity is O(n).