[Facebook] Maximum Size Subarray Sum Equals k

Problem: Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4  
Explanation: [1,-1,5,-2] is the longest subarray with sum 3.

Input: nums = [2,-1,2,1], k = 1
Output: 2
Explanation: [2,-1] or [-1,2] are the longest subarrays with sum 1.

Approach: We can use hashing here. Basically we will store the [0...i] cumulative sum as key and index i as the value. We can always check if current cumulative sum - k is in the hash table or not. If yes, we can get its index from hash table. The subarray length will be i - value_index + 1. Now we just need to get the max of such subarray's length.

Implementation in C#:

    public int maxLen(int[] arr, int n, int k)

    {

        int length = arr?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        var sumMap = new Dictionary<int, int>();

        int sum = 0;

        int maxLen = 0;

        for (int i = 0; i < length; ++i)

        {

            sum += arr[i];

            if (sum == k)

            {

                maxLen = i + 1;

            }

            else if (sumMap.ContainsKey(sum - k))

            {

                maxLen = Math.Max(maxLen, i - sumMap[sum - k]);

            }

            

            if (!sumMap.ContainsKey(sum))

            {

                sumMap[sum] = i;

            }

        }

        return maxLen;

    }

Complexity: O(n)