(一维路径求和) 和为K的子数组

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         /**
  4.             前缀和+hash表
  5.             对于一维问题（一位区间求两个数之和是否==t），我们求出前缀和si
  6.             转换为si - sj = t,用哈希表存放si出现的次数,同时对于si,累加出哈希表中key=si-t的value(次数)  
  7.             因此扫描一遍时间复杂度o(n)
  8.          */
  9.         int n = nums.length;
  10.         int[] s = new int[n + 1];
  11.         int res = 0;
  12.         HashMap<Integer, Integer> map = new HashMap<>();
  13.         // 前缀和本身就是k
  14.         map.put(0, 1);
  15.         for (int i = 1; i <= n; i ++){
  16.             s[i] = nums[i - 1] + s[i - 1];
  17.             if (map.containsKey(s[i] - k)) res += map.get(s[i] - k);
  18.             map.put(s[i], map.getOrDefault(s[i], 0) + 1);
  19.         }
  20.         return res;
  21.     }
  22. }

(二维路径求和：hash+dfs+前缀和)路径总和 III

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     HashMap<Integer, Integer> map = new HashMap<>(); 
  18.     int res = 0, t;
  19.     public int pathSum(TreeNode root, int targetSum) {
  20.         /**
  21.             对于一维问题（一位区间求两个数之和是否==t），我们求出前缀和si
  22.             转换为si - sj = t,用哈希表存放si出现的次数,同时对于si,累加出哈希表中key=si-t的value(次数)  
  23.             因此扫描一遍时间复杂度o(n)
  24.             对于二维树,在dfs过程中,对于每一个点,我们要求当前点为根节点的路径中是否又满足题目要求的点
  25.             这条路径就是一维问题,因此dfs中,我们存入每个点的前缀和出现的次数,同时对于节点i,我们只需要找出key = si - t的value(次数)
  26.             回溯的过程中再把当前点的前缀和从哈希表中删掉，更新前缀和，因为当前点不算在路径里面了。
  27.          */ 
  28.         //  哨兵节点，表示一个数都没有的前缀和，用于dfs过程中当前点就是t
  29.         map.put(0, 1);
  30.         this.t = targetSum;
  31.         dfs(root, 0);
  32.         return res;
  33.     }
  34.     public void dfs(TreeNode root, int pfSum){
  35.         if (root == null) return ;
  36.         pfSum += root.val;
  37.         // 先加再存，防止出现t == 0，重复计算的情况
  38.         res += map.getOrDefault(pfSum - t, 0);
  39.         map.put(pfSum, map.getOrDefault(pfSum, 0) + 1);
  40.         dfs(root.left, pfSum);dfs(root.right, pfSum);
  41.         // 回溯
  42.         map.put(pfSum, map.getOrDefault(pfSum, 0) - 1);
  43.     }
  44. }