什么是前缀和

给定数组 arr，那么 preSum 为前缀和数组；

preSum[i] = arr[0] + arr[1] + ... + arr[i];

采用空间换时间的方式，提高计算区间和的效率。

和为K的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 定义前缀和map，key为preSum，value为次数
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, preSum = 0;
        for (int n : nums) {
            preSum += n;
            res += map.getOrDefault(preSum - k, 0);
            // 如果发现当前的前缀和已经等于k，结果加1
            if (preSum == k) res++;
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return res;
    }
}

统计「优美子数组」

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // preSum代表当前前缀符合条件的子数组个数
        int res = 0, preSum = 0;
        for (int n : nums) {
            // 奇数preSum加一
            if (n % 2 == 1) preSum += 1;
            res += map.getOrDefault(preSum - k, 0);
            if (preSum == k) res++;
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return res;
    }
}

和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // map存前缀余数，key为余数，value为次数
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, preSum = 0;
        for (int n : nums) {
            preSum += n;
            // 避免负数干扰！！
            int rest = (preSum % k + k) % k;
            res += map.getOrDefault(rest, 0);
            if (rest % k == 0) res++;
            map.put(rest, map.getOrDefault(rest, 0) + 1);
        }
        return res;
    }
}

路径总和 III

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // map存遍历节点前缀和，前序遍历
        return dfs(root, targetSum, new HashMap<>(), 0);
    }

    private int dfs(TreeNode node, int targetSum, Map<Integer, Integer> prefix, int curr) {
        if (node == null) {
            return 0;
        }
        curr += node.val;
        int res = prefix.getOrDefault(curr - targetSum, 0);
        if (curr == targetSum) res++;
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        res += dfs(node.left, targetSum, prefix, curr);
        res += dfs(node.right, targetSum, prefix, curr);
        // 记得恢复
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return res;
    }
}