Code to find longest sub-array having given sum in an integer array

1. Write code to find longest contiguous sub-array having given sum in an integer array.

Example:  If array is {3, -5, 2, 3, 1, 4}, and given sum is 4:
   There are many contiguous sub arrays having sum=0  like   {3,1}.  {3,-5,2,3,1}, {4}. So output will be the longest among them being {3,-5,2,3,1}.

Ans)
  We can come up with brute force approach of O(n^2) by checking sum of each sequence for all the elements in the array. But that definitely is not efficient.

So one efficient solution in O(n):

1. Form a new array such that a[i] = a[i-1]+a[i-2]+.. for each element a[i].
2. Now if we check the new array, we can see that whichever elements have the difference of given sum, all elements between those elements will add up to that sum. So our solution would be to find such pairs whose difference is given sum in the new array and find the farthest among them. So to make it efficient, we can use hash map to store sums till now instead of storing in a new array.

So taking example above:

{3, -5, 2, 3, 1, 4}

New Array: {0,3, -2, 0, 3, 4, 8}
If given sum is 4, we can find all pairs whose difference is 4. Or in case of hash map implementation, for each element a[i], check if (a[i]+4) or (a[i]-4) is present in the hash map.

Sample Code in JAVA
(Logic is little bit modified from whatever explained above. Here I'm using a hash map to store sums and in one parse of the array itself, finding the longest sub-array)



    private int givenSum = 4;
    private int[] mArray = { 1, 3, 3, -6, 1, 2 };
    private int maxLen = 0;
    private int maxStrtIndex = -1;

   
    // Hashmap where key is sum till a particular index and value is the 1st
    // index in the mArray where this sum is met
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();



    private void findLongestSubArray() {
        int sum = 0;
        for (int i = 0; i < mArray.length; i++) {
            // Add this sum to hashmap if its not there already.We need to add
            // only first time since we're interested in finding longest
            // subsequence
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
            sum += mArray[i];
            // Check for elements with sum difference as given sum is present in
            // array and if so, get the index of such an element
            int strtIndex = -1;
            if (map.containsKey(sum - givenSum)) {
                strtIndex = map.get(sum - givenSum);
            }
            if (map.containsKey(sum + givenSum)) {
                int tmp = map.get(sum + givenSum);
                // Get the least start index value so that length will be max
                if (tmp < strtIndex) {
                    strtIndex = tmp;
                }
            }
            if (strtIndex != -1) {
                int seqLen = i + 1 - strtIndex;
                // Update max len in case this is the max sub array
                if (seqLen > maxLen) {
                    maxLen = seqLen;
                    maxStrtIndex = strtIndex;
                }
            }
        }
    }