MaximumSizeSubarraySumEqualsk.java

package hashing;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by gouthamvidyapradhan on 18/10/2017.
 * 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.

 Note:
 The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

 Example 1:
 Given nums = [1, -1, 5, -2, 3], k = 3,
 return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

 Example 2:
 Given nums = [-2, -1, 2, 1], k = 1,
 return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

 Follow Up:
 Can you do it in O(n) time?
 */
public class MaximumSizeSubarraySumEqualsk {

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        int[] A = {1,-1,5,-2,3};
        System.out.println(new MaximumSizeSubarraySumEqualsk().maxSubArrayLen(A, 10));
    }

    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> index = new HashMap<>();
        int sum = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i];
            index.putIfAbsent(sum, i);
        }
        sum = 0;
        int ans = 0;
        for(int i = 0; i < nums.length; i ++){
            sum += nums[i];
            if(sum == k){
                ans = Math.max(ans, i + 1);
            } else{
                int exp = sum - k;
                if(index.containsKey(exp)){
                    int farLeft = index.get(exp);
                    if(farLeft < i){
                        ans = Math.max(ans, i - index.get(exp));
                    }
                }
            }
        }
        return ans;
    }

}