数据结构---前缀和

前缀和即为在该元素之前的数组和

来源：560. 和为 K 的子数组 - 力扣（LeetCode）

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n+1];
        for (int i = 0; i < n; i++) {
            s[i+1] = nums[i]+s[i];
        }
        int ans = 0;
        Map<Integer,Integer>map = new HashMap<>();
        for (int i = 0; i < s.length; i++) {
            ans += map.getOrDefault(s[i]-k,0);
            map.put(s[i],map.getOrDefault(s[i],0)+1);
        }
        return ans;
    }
}

问：为什么要把 0 加到哈希表中？

答：这里的 0 相当于前缀和数组中的 s[0]=0。举个最简单的例子，根节点值为 1，targetSum=1。如果不把 0 加到哈希表中，按照我们的算法，没法算出这里有 1 条符合要求的路径。也可以这样理解，要想把任意路径和都表示成两个前缀和的差，必须添加一个 0，否则当路径是前缀时（从根节点开始的路径），没法减去一个数，具体见 前缀和及其扩展 中的讲解。

问：为什么代码中要先更新 ans，再更新 cnt？

答：在 targetSum=0 的情况下，这俩谁先谁后都可以。但如果 targetSum=0，假设根节点值为 1，如果先把 cnt[1] 增加 1，再把 ans 增加 cnt[s−targetSum]=cnt[1]=1，就相当于我们找到了一条和为 targetSum=0 的路径，但和为 0 的路径是不存在的。另一种理解方式是，空路径的元素和等于 0，我们把这个 0 当作了符合要求的路径，但题目要统计的是非空路径。

问：代码中的「恢复现场」用意何在？

答：如果不恢复现场，当我们递归完左子树，要递归右子树时，cnt 中还保存着左子树的数据。但递归到右子树，要计算的路径并不涉及到左子树的任何节点，如果不恢复现场，cnt 中统计的前缀和个数会更多，我们算出来的答案可能比正确答案更大。

作者：灵茶山艾府
链接：https://leetcode.cn/problems/path-sum-iii/solutions/2784856/zuo-fa-he-560-ti-shi-yi-yang-de-pythonja-fmzo/
 

private int ans;
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer>map = new HashMap<>();
        map.put(0L,1);
        dfs(root,0,targetSum,map);
        return ans;
    }
    private void dfs(TreeNode node,long s,int targetSum,Map<Long,Integer>cnt){
        if(node == null){
            return;
        }
        s += node.val;
        ans += cnt.getOrDefault(s-targetSum,0);
        cnt.put(s,cnt.getOrDefault(s,0)+1);
        dfs(node.left,s,targetSum,cnt);
        dfs(node.right,s,targetSum,cnt);
        cnt.put(s,cnt.get(s)-1);
    }