# Prefix Sum

Subarray Sum Equals K

Given an array of integers `nums` and an integer `k`, return the total number of continuous subarrays whose sum equals to `k`.

`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;    }}`

Path sum 3

Given the `root` of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values along the path equals `targetSum`.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

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

--

--