0325. Maximum Size Subarray Sum Equals k

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k

Description

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

Example 1:

**Input:** nums = [1,-1,5,-2,3], k = 3
**Output:** 4
**Explanation:** The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

**Input:** nums = [-2,-1,2,1], k = 1
**Output:** 2
**Explanation:** The subarray [-1, 2] sums to 1 and is the longest.

Constraints:

• 1 <= nums.length <= 2 * 105

• -104 <= nums[i] <= 104

• -109 <= k <= 109

ac

range sum, current sum - old sum = k. Why 2 pointers fail here? because cannot decide how to move the pointers.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        // edge cases
        if (nums == null || nums.length == 0) return 0;

        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) max = i + 1;

            int oldSum = sum - k;  // currentSum - oldSum = k
            if (map.containsKey(oldSum)) max = Math.max(max, i - map.get(oldSum));
            if (!map.containsKey(sum)) map.put(sum, i);  // if contains before, skip
        }

        return max == Integer.MIN_VALUE ? 0 : max;
    }
}

/*
edge cases
hashmap
*/