当前位置：首页 > article >正文

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

article 2024/9/24 5:33:22

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);
    }