SubarraySum.java

// O(n) time solution
class SubarraySum {
 public int maxSubArrayLen(int[] nums, int k) {
 if (nums == null || nums.length == 0) {
 return 0;
 }
 
 Map<Integer, Integer> map = new HashMap<>();
 int len = 0;
 int sum = 0;
 
 map.put(0, -1); // eliminates the need to check sum == k
 for (int i = 0; i < nums.length; i++) {
 sum += nums[i];
 if (map.containsKey(sum - k)) {
 len = Math.max(len, i - map.get(sum - k));
 }
 if (!map.containsKey(sum)) {
 map.put(sum, i);
 }
 }
 return len;
 }
}