Prefix Sum

class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0,1);
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum+=nums[i];
if(map.containsKey(sum-k)) {
count+=map.get(sum-k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
class Solution {
HashMap<Integer,Integer> map;
int target=0;
int count=0;
public int pathSum(TreeNode root, int targetSum) {
map= new HashMap();
map.put(0,1);
this.target=targetSum;
sum(root,0);
return count;

}
public void sum(TreeNode root, int curr){
if(root!=null){
curr=curr+root.val;
if(map.containsKey(curr-target)){
count+=map.get(curr-target);
}
map.put(curr,map.getOrDefault(curr,0)+1);
sum(root.left,curr);
sum(root.right, curr);
map.put(curr, map.get(curr)-1);

}
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store