Pattern: Array

Longest Subarray with sum K

class Solution {
    public int longestSubarray(int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);//handle subarray that start from index 0: edge case when the length is 1 of the subarray that sums to k
        //example arr[] = [3], k =3, map=[{0,-1}], at 0 prefixSum = 3 and 3-3 = 0 i.e currentIndex i.e 0 - map.get(0) = -1 = 0-(-1) = 1 i.e the length of the subarray
        int prefixSum = 0;
        int len = 0;
        for(int i = 0;i<arr.length;i++){
            prefixSum+=arr[i];
            if(map.containsKey(prefixSum-k)){
                len = Math.max(len, i-map.get(prefixSum-k));
            }
            if(!map.containsKey(prefixSum)) map.put(prefixSum, i);
        }

        return len;

    }
}

Subarray sum equal to k
note: this is exactly same as the above one with slight twist

class Solution {
    public int subarraySum(int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int prefixSum = 0;
        int len = 0;
        int count = 0;
        map.put(0,1);
        for(int i = 0;i<arr.length;i++){
            prefixSum+=arr[i];
            if(map.containsKey(prefixSum-k)){
                //len = Math.max(len, i-map.get(prefixSum-k));
                count+=map.get(prefixSum-k);
            }
            map.put(prefixSum, map.getOrDefault(prefixSum, 0)+1);
            // if(!map.containsKey(prefixSum)) map.put(prefixSum, i);
        }

        return count;
    }
}

1.