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.
