325. Maximum Size Subarray Sum Equals k

Question

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not 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.

Algorithm

This is a sub array question.

Where is something like array - sum you can try to leverage pre-sum. In this question, we are also given a target. At the very beginning, I tried use two pointers but to doesn't work. The slight different of two pointers question and pre sum is obvious actually, preSum is used when the questions refer sum of sub array.

So first we try to build a new array called preSum. Then the issue becomes based on this array. Then I got trapped by using two pointers again. Use a overall view or refresh view to this question. You are given an array of numbers and a target, find the longest distance of elements in the array that the later number minus previous number can be that target, in other words, target + showed number equals current number, return the distance.

Ah, it's much like two sum, we may leverage map to reduce the time complexity and it's can use it actually.

To optimized the code, you don't really need the preSum array, you can record each preSum and its index into map.

Code1(TLE)

Basically this is a O(n*n) time complexity solution. The worst case happens when in the loop, while left < i, no sum(temp) equals k, then left should go start from the 0 to the i.

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int temp = sum;
            int left = -1;
            while (left < i) {
                if (temp == k) {
                    res = Math.max(i - left, res);
                    break;
                } 
                temp -= nums[++left];
                
            }
        }
        return res;
    }
}

Code2

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