例题1.和为k的子数组

链接：LeetCode560.和为k的子数组

思路

经典的一维前缀和问题：求以i为右端点的区间，其权值和为目标值
假设区间[j+1,i]的和为target，则说明s[i] - s[j] = target，即s[j] = s[i] - target
我们要求的问题就转换成了求区间[0,i]中有多少个j，使得s[j] = s[i] - target
我们只需要在遍历数组的同时，把前缀和的出现次数都存入哈希表中
在遍历每个i的时候，就可以在O(1)的时间复杂度内查询到s[i]-target在哈希表中出现了几次，全部累加起来就是答案

注意：
1.需要添加一个哨兵(0,1)，如果s[i] - target = 0，也能记录到子数组的个数
2.一定要先统计子数组个数，再更新哈希表，否则如果target为0，会统计到错误答案

看到这里你可能会觉得这个思路似曾相识，可以回头看看LeetCode1.两数之和
两数之和只需要记录一个数是否出现过，而这题需要记录前缀和的出现次数，算是一个扩展吧

Java代码

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

例题2.路径总和Ⅲ

链接：LeetCode437.路径总和Ⅲ

思路

题目明确说明，路径一定是自上而下，不一定需要经过根节点
对于每一条自上而下的路径，都可以用上一题的思路来解决
所以我们可以利用dfs对树进行前序遍历，遍历的过程中记录前缀和并保存在哈希表中
在递归返回的时候，需要删除下层节点所在路径的前缀和，以免重复记录

Java代码

class Solution {
    int res = 0;
    Map<Integer,Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int sum) {
        map.put(0,1);
        dfs(root, sum, 0);
        return res;
    }

    void dfs(TreeNode root, int sum, int cur){
        if(root == null) return;
        cur += root.val;
        if(map.containsKey(cur-sum)) res += map.get(cur-sum);
        map.put(cur, map.getOrDefault(cur,0)+1);
        dfs(root.left, sum, cur);
        dfs(root.right, sum, cur);
        map.put(cur, map.get(cur)-1);
    }
}