Find maximum length sub array having given sum

Given an array of integers, find the maximum length of sub array whose sum equals to a given sum

Example – A = [ 5, 6, -5, 5, 3, 5, 3, -2, 0 ] and sum = 8

All sub arrays are [-5,5,3,5] , [5,3], [3,5] . Max length sub array is [-5,5,3,5] (4)

Approaches

1. Naive O(n^2) – Traverse through all the sub arrays and find the max length sub array.
2. Linear O(n) (Hashing) – While traversing through the array maintain a hash map or dictionary to store sum as key and the ending index of sub array as the value. Check if (curr_sum – given_sum) is present in the hash map and check for the length of the sub array from current index and index at (curr_sum-given_sum). Return the sub_array with max length.