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);

}
}
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Intro to Convolutional Coding — Part II

Just another post of TestNG bag of tricks

What is Software Testing? Part 1: Importance and Types

Unleashing the power of Redis x Django

Integrate JWT in SpringBoot to realize Token verification (Interceptor)

The Top 3 toughest challenges into my career change

Learn to code by making a 2D space shooter game.

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
Abhinay Gupta

Abhinay Gupta

More from Medium

The Art Of Programming #10

WHAT’S SAFER AND PREFERABLE TO START WITH?

Advent Of Code 2021 — Smoke Basin — Puzzle 9

C Language “hello world” Program Explained Step by Step All Statements