一、和为K的子数组
560：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
class Solution {public int subarraySum(int[] nums, int k) {//key为前缀和，value为此前缀和的个数Map<Integer,Integer> map = new HashMap<>();map.put(0,1);int prefixsum = 0;int result = 0;for(int i=0;i<nums.length;i++){prefixsum += nums[i];//有前缀和是prefixsum-kif(map.containsKey(prefixsum - k)){result += map.get(prefixsum - k);}if(map.containsKey(prefixsum)){map.put(prefixsum,map.get(prefixsum)+1);}else{map.put(prefixsum,1);}}return result;}
}二、路径总和III
437：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
前缀和：
class Solution {HashMap<Integer,Integer> map = new HashMap<>();int result = 0;public int pathSum(TreeNode root, int targetSum) {map.put(0,1);dfs(root,targetSum,0);return result;}public void dfs(TreeNode root,int targetSum,int prefixsum){if(root==null){return ;}prefixsum += root.val;result += map.getOrDefault(prefixsum-targetSum,0);//当自己的前缀和加入map中map.put(prefixsum,map.getOrDefault(prefixsum,0)+1);dfs(root.left,targetSum,prefixsum);dfs(root.right,targetSum,prefixsum);//将自己对应前缀和个数-1，不能防碍兄弟节点的查询map.put(prefixsum,map.get(prefixsum)-1);}
}双重递归：
class Solution {int result = 0;//前序遍历public int pathSum(TreeNode root, int targetSum) {if(root == null){return 0;}search(root,targetSum);pathSum(root.left,targetSum);pathSum(root.right,targetSum);return result;}//以root为根搜索是否有解public void search(TreeNode root,int targetSum){if(root==null){return ;}targetSum -= root.val;if(targetSum==0){result++;}search(root.left,targetSum);search(root.right,targetSum);}}