Problem

Given an array of integers nums and an integer k, find the maximum size of a contiguous subarray where the sum of the subarray's elements is equal to k. If no such subarray exists, return 0.

You must solve this problem in linear time complexity.

Example

Input: nums = [1, -1, 5, -2, 3], k = 3

Output: 4

Explanation: The subarray [1, -1, 5, -2] sums to 3, which is equal to k.

Solution

To solve this problem efficiently, we can use a cumulative sum approach and store the frequency of each cumulative sum we encounter.

We will initialize a variable max_length to keep track of the maximum subarray size. Also, we will maintain a variable cumulative_sum to store the cumulative sum obtained from the beginning of the array.

We'll iterate through the array nums, updating cumulative_sum by adding the current element at each iteration. Then, we check if (cumulative_sum - k) exists in a hashmap. If it does, it means there is a subarray with sum k that ends at the current index. We update max_length if the current subarray size is larger.

Finally, we return max_length, which will hold the maximum subarray size with a sum equal to k. If no such subarray exists, max_length would be 0.

Here is the step-by-step algorithm:

1. Create a hashmap sum_count with one initial key-value pair: {0: 1}.
2. Initialize variables: max_length = 0, cumulative_sum = 0.
3. Iterate through each element num in the input array nums:
   • Update cumulative_sum by adding the current element: cumulative_sum += num.
   • Check if cumulative_sum - k exists in sum_count. If it does, increment max_length by the value of sum_count[cumulative_sum - k].
   • Increment the value of sum_count[cumulative_sum] by 1.
4. Return max_length.

Let's implement this in code:

def max_subarray_sum(nums, k):
    sum_count = {0: 1}  # Initialize hashmap with a single key-value pair

    max_length = 0
    cumulative_sum = 0

    for num in nums:
        cumulative_sum += num
        
        if cumulative_sum - k in sum_count:
            max_length += sum_count[cumulative_sum - k]
        
        sum_count[cumulative_sum] = sum_count.get(cumulative_sum, 0) + 1
    
    return max_length

The time complexity of this solution is O(n), where n is the size of the input array nums. This is because we perform a single pass through the nums array.

Now, let's test our function with the example provided:

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

print(max_subarray_sum(nums, k))  # Output: 4

The function correctly returns the maximum size of a subarray with sum equal to 3, which is 4.