Brute Force Solution

A naive approach to solve this problem is to iterate through all possible subarrays and check if their sum equals k. This involves two nested loops.

Algorithm:

1. Iterate through the array using a starting index i.
2. For each i, iterate through the array from i to the end using index j.
3. Calculate the sum of the subarray from i to j.
4. If the sum equals k, increment the count.
5. Return the count.

Code (Python):

def subarray_sum_brute_force(nums, k):
    count = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            current_sum = 0
            for l in range(i, j + 1):
                current_sum += nums[l]
            if current_sum == k:
                count += 1
    return count

Time Complexity: O(n^3), due to the three nested loops.

Space Complexity: O(1), as it uses constant extra space.

Optimal Solution: Using Prefix Sum and Hash Map

An optimal approach involves using a hash map to store prefix sums and their frequencies. This reduces the time complexity significantly.

Algorithm:

1. Initialize a hash map prefix_sums to store prefix sums and their counts. Initialize prefix_sums[0] = 1 to handle cases where a subarray starting from the beginning sums to k.
2. Initialize current_sum = 0 and count = 0.
3. Iterate through the array nums.
4. Update current_sum by adding the current element.
5. Check if current_sum - k exists in prefix_sums. If it does, it means there's a subarray ending at the current index with a sum of k. Increment count by the frequency of current_sum - k in prefix_sums.
6. Update the frequency of current_sum in prefix_sums.
7. Return count.

Code (Python):

def subarray_sum_optimal(nums, k):
    prefix_sums = {0: 1}
    current_sum = 0
    count = 0
    for num in nums:
        current_sum += num
        if current_sum - k in prefix_sums:
            count += prefix_sums[current_sum - k]
        if current_sum in prefix_sums:
            prefix_sums[current_sum] += 1
        else:
            prefix_sums[current_sum] = 1
    return count

Time Complexity: O(n), as it iterates through the array once.

Space Complexity: O(n), in the worst case, the hash map prefix_sums can store n different prefix sums.

Edge Cases

• Empty Array: The code should work correctly for an empty array, returning 0.
• All Positive or All Negative Numbers: The algorithm should handle cases where all numbers are positive or all are negative.
• Zero Sum Subarrays: The algorithm correctly counts subarrays that sum to zero.
• k = 0: The algorithm correctly counts subarrays that sum to zero when k is zero.

Example

nums = [1, 2, 3, -3, 2, 1], k = 3

Using the optimal solution:

1. prefix_sums = {0: 1}, current_sum = 0, count = 0
2. num = 1, current_sum = 1. prefix_sums = {0: 1, 1: 1}
3. num = 2, current_sum = 3. current_sum - k = 0. count = 1. prefix_sums = {0: 1, 1: 1, 3: 1}
4. num = 3, current_sum = 6. prefix_sums = {0: 1, 1: 1, 3: 1, 6: 1}
5. num = -3, current_sum = 3. current_sum - k = 0. count = 2. prefix_sums = {0: 1, 1: 1, 3: 2, 6: 1}
6. num = 2, current_sum = 5. prefix_sums = {0: 1, 1: 1, 3: 2, 6: 1, 5: 1}
7. num = 1, current_sum = 6. current_sum - k = 3. count = 2 + 2 = 4. prefix_sums = {0: 1, 1: 1, 3: 2, 6: 2, 5: 1}

Result: 4