[JAVA] double 100% solution using prefix travsersing + hashMap
For an array [2, -1, 3, -2, 1], given the targer value tar = 1, if you were asked to find out all subarrays whose sum equals to tar, what will you do?\nThe basi
For an array [2, -1, 3, -2, 1], given the targer value tar = 1, if you were asked to find out all subarrays whose sum equals to tar, what will you do?\nThe basic idea is that, let sum[i] be the sum of elements from 0 to i; Then sum[j] - sum[i] is the sum of elements from i to j; if sum[j] - sum[i] = tar, then the subarray of [i, j] is one of the expected array. If you store sum[i] in a HashMap with key sum[i] and  frequence f, every time you estimate new sum[j], you just need to check if the HashMap contains the key sum[j] - tar, if it does, then we will have f different ways to get the tar.\nApplying the same idea to tree. By using prefix travsering, we can regrard the tree as an array.\n```java\nclass Solution {\n    public int pathSum(TreeNode root, int sum) {\n        HashMap<Integer, Integer> map = new HashMap<>();\n        map.put(0, 1);\n        return pathSum(root, 0, sum, map);\n    }\n    private int pathSum(TreeNode root, int curSum, int sum, HashMap<Integer, Integer> map) {\n        if (root == null) return 0;\n        curSum += root.val;\n        int res = map.getOrDefault(curSum - sum, 0);\n        map.put(curSum, map.getOrDefault(curSum, 0) + 1);\n        res += pathSum(root.left, curSum, sum, map) + pathSum(root.right, curSum, sum, map);\n        map.put(curSum, map.get(curSum) - 1);\n        return res;\n    }\n}\n```
[]