LeetCode复习 前缀和系列

#238 除自身以外数组的乘积

 public int[] productExceptSelf(int[] nums) {
  int[] res = new int[nums.length];
        int k = 1;
        //算出左边的乘积
        for (int i = 0; i < nums.length; i++) {
            res[i] = k;
            k *= nums[i];
        }
        k = 1;
        //算出右边的乘积再和左边的相乘
        for (int i = nums.length - 1; i >= 0; i--) {
            res[i] *= k;
            k *= nums[i];
        }
        return res;
    }

#560 和为 K 的子数组

 public int subarraySum(int[] nums, int k) {
Map map = new HashMap<>();
        map.put(0,1);
        int preSum = 0;
        int res = 0;
         for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum-k)) {
                res += map.get(preSum-k);
            }
             map.put(preSum,map.getOrDefault(preSum,0)+1);
        }
        return res;
    }

一维前缀和

static class NumArray {
        int[] preSum;
        public NumArray(int[] nums) {
            preSum = new int[nums.length];
            preSum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                preSum[i] = nums[i] + preSum[i-1];
            }
            System.out.println();
        }

        public int sumRange(int left, int right) {
           return left == 0 ? preSum[right] : preSum[right] - preSum[left-1];
        }
    }

二维前缀和

class NumMatrix {
        int[][] preSum;
        public NumMatrix(int[][] matrix) {
            int r = matrix.length;
            int c = matrix[0].length;
            preSum = new int[r + 1][c + 1];
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] - preSum[i][j] + matrix[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1];
        }
    }

路径总和|||

int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        //key是前缀和 value是该前缀和出现的次数
        Map preSumMap = new HashMap<>();
        //前缀和为0的出现了一次，就是一个节点都没有时
        preSumMap.put(0,1);
        pathSumDfs(root,preSumMap,targetSum,0);
        return count;
    }

    private void pathSumDfs(TreeNode root, Map preSumMap, int target, int curSum) {
        if (root == null) {
            return;
        }
        curSum += root.val;
        //先找后更新前缀和
        if (preSumMap.containsKey(curSum - target)) {
            count += preSumMap.get(curSum - target);
        }
        preSumMap.put(curSum,preSumMap.getOrDefault(curSum,0) + 1);
        pathSumDfs(root.left,preSumMap,target,curSum);
        pathSumDfs(root.right,preSumMap,target,curSum);
        //回溯恢复现场,去除当前节点的前缀和数量，因为这个路径不可能是别的路径的前缀了
        //恢复现场是因为路径方向必须是向下的（只能从父节点到子节点）一个节点必须是另一个节点的祖先节点
        //例如遍历完最左边的3，然后遍历-2时是不包含21这条前缀和，因为路径只能从父节点到子节点，不能从子节点到父节点再到子节点
        preSumMap.put(curSum,preSumMap.getOrDefault(curSum,0) - 1);
    }