[Java] Hash Table + Prefix Sum


  • 0
    Z

    Iterate through the array. Calculate prefix sums as I iterate. Use a hash map to keep track of prefix sum => index. For each prefix sum, check if map contains a key that equals prefix sum - k. If so, the length of the sub-array is index - map.get(prefixSum - k). Put current prefix sum => index into the map only if prefix sum doesn't exist in the map yet. Initialize the hash map with an entry 0 => -1.

    Further thoughts: because I'm not using all of the prefix sums, I only need a variable to keep track of the previous sum.

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

Log in to reply
 

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