Java O(n), like other subarray sum problem


  • 0
    K

    There is a variety of subarray sum problem utilize similar technology:

    [325] Maximum Size Subarray Sum equal K
    https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/?tab=Description

    We can first calculate array prefix sum, then the problem is convert to
    finding presum[j] - presum[i] == target where j - i is maximized.

    The above equation can borrow O(n) two sum solution, which use hashmap to store target + presum[i].

    Another trick applied in this problem is, when calculating prefix sum, we add -1 instead of 0, when nums[i] == 0. With this trick , we can formulate problem as presum[j] - presum[i] == 0.

    public int findMaxLength(int[] nums) {
            if (nums == null || nums.length <= 1) return 0;
            int len = nums.length;
            
            // Store the 
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0,0);
            int res = 0;
            
            // Calculate the prefix on the fly.
            int sum = 0;
            
            for (int i = 1; i <=len; i++ ) {
                sum = sum + (nums[i-1] == 0 ? -1 : 1);
                if (map.containsKey(sum)) {
                    res = Math.max(i - map.get(sum), res);        
                } else {
                    map.put(sum, i);
                }  
            }
            
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.