从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/
1
2
3
4

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

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

2.1 疑惑

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

	//代码片段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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

	//代码片段2
    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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 为什么对于当前这道题dfs的题，回溯要等到返回到当前层，而全排列这道题是从子节点返回后就需要回溯？

lc46. 全排列的题解如下：

class Solution {
    List<List<Integer>>res;
    List<Integer>list;
    Set<Integer>set;
    public List<List<Integer>> permute(int[] nums) {
        res=new ArrayList<>();
        list=new ArrayList<>();
        set=new HashSet<>();
        dfs(nums,0);
        return res;
    }

    void dfs(int[]nums,int s){
        if(list.size()==nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            System.out.println("i:"+i+", nums[i]:"+nums[i]+", list.toString():"+list.toString());
            set.add(nums[i]);
            dfs(nums,i);
            set.remove(nums[i]);
            list.remove(list.size()-1);
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

答：是因为Java 中的基本数据类型和字符串是不可变的，当它们被作为参数传递给方法时，实际上是传递的值的拷贝，对于2.1中的代码片段1，因为ns变量是值传递，且ns变量等于从根节点到当前节点的路径和，所以当这个时候进行put操作的时候，put中的key是当前的路径和，这个路径和对其子树中的所有节点都有效，所以必须等到左右子树的节点都遍历完后当前节点的路径不再有用且必须把map中的键值对做回溯操作。

而全排列这道题中，因为list是一个引用传递，所以当遍历完左子树时，如果list没有回溯，则遍历到右子树时，list中会有左子树中的节点，从而影响结果。

2.3 其他的类似于这道题的回溯方式的题目：LC79. 单词搜索

 public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack2(board, 0, i, j, vis, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean backtrack2(char[][] board, int i, int p, int q, boolean[][] vis, String word) {
        if(i==word.length()){
            return true;
        }

        if(p<0||p>=board.length||q<0||q>=board[0].length||word.charAt(i)!=board[p][q]||vis[p][q]){
            return false;
        }

        vis[p][q]=true;

        for(int k=0;k<4;k++){
            int np=p+dirs[k];
            int nq=q+dirs[k+1];
            boolean f=backtrack2(board,i+1,np,nq,vis,word);
            if(f){
                return true;
            }
        }
        vis[p][q]=false;
        return false;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37