从lc560“和为 K 的子数组“带你认识“前缀和+哈希表“的解题思路

本文主要是介绍从lc560“和为 K 的子数组“带你认识“前缀和+哈希表“的解题思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 前缀和+哈希表解题的几道题目：建议集中练习

 560. 和为 K 的子数组：https://leetcode.cn/problems/subarray-sum-equals-k/
1248. 统计「优美子数组」: https://leetcode.cn/problems/count-number-of-nice-subarrays/
1249. 和可被 K 整除的子数组(利用同余定理)：https://leetcode.cn/problems/subarray-sums-divisible-by-k/
1250. 连续的子数组和：https://leetcode.cn/problems/continuous-subarray-sum/

2 在树中利用"前缀和+哈希表"的解题思路 - “437. 路径总和 III” ？

LeetCode上有一道题目和“560. 和为 K 的子数组”在解法上非常类似，那就是“437. 路径总和 III”。这道题目是关于二叉树的，要求找到二叉树中和为K的路径的数量。其解法也是利用前缀和和哈希表。

2.1 疑惑

下面两个回溯代码有啥区别？

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

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