Link

Medium Hash Table

Google

2020-05-26

325. Maximum Size Subarray Sum Equals k

Similar Question: LeetCode Question 525

Question:

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:

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.

Follow Up:
Can you do it in O(n) time?


Solution:

Using the similar idea as LeetCode Question 525, we need to use hash table to record the first sum value and its corresponding index. Then if the hash table has the difference between current sum and k, we compare with the result to find the maximum value.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int result = 0;
        int sum = 0;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        map.put(0,-1);
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                result = Math.max(result, i - map.get(sum - k));
            } 
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return result;
    }
}