前缀和与差分

前缀和与差分都是数组的重要技巧。

前缀和

原理介绍

（1）是什么？

前缀和说白了就是数组前N项和。

给定数组 $A_i$ 则前缀和为 $S_i = \sum\limits_{k=0}^{i}a_k$

（2）能干什么？

前缀和能快速计算数组区间和，将线性时间复杂度优化为常数时间复杂度。

记数组第i个元素到第j个元素之间的和为 $f(i,j)$， 则 $f(i,j) = S_{j}-S_{i-1}$ ，其中i从0开始。

为了避免-1的下标，修改前缀和 $S_i = \sum\limits_{k=0}^{i-1}a_k，i=1,2,3…$，并令$S_0 = 0$，我们得到$f(i,j) = S_{j+1}-S_{i}$

（3）伪代码

sum[0] = 0;
sum[1] = num[0];
sum[k] = num[0]+...+ num[k-1];

那么从num[i] 到 num[j]的和为sum[j+1] - sum[i]

区域和检索

https://leetcode.cn/problems/range-sum-query-immutable/

class NumArray {
    public int len;
    public int[] nums;
    public NumArray(int[] nums) {
        len = nums.length;
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int[] sum = new int[1+len];
        // sum[k] means a1+...ak-1
        sum[0] = 0; 
        for(int i=1; i<=len; ++i){
            sum[i] = sum[i-1]+ nums[i-1];
        }
        return sum[right+1]-sum[left];
    }
}

从此题中就可以看出，前缀和适用于频繁求数组区间和的场景。如果只求一次区间和，那么线性累加反而更快。

和为K的子数组

https://leetcode.cn/problems/QTMn0o/description/

（1）暴力遍历

class Solution {
    public int subarraySum(int[] nums, int k) {
        int N = nums.length;
        int[] sum = new int[N+1];
        for(int i=1; i<=N; ++i)
            sum[i] = sum[i-1] + nums[i-1];
        // 遍历所有的可能区间[i, j]
        int ans = 0;
        for(int i=0; i<N; ++i){
            for(int j=i; j<N; ++j){
                if((sum[j+1]-sum[i]) == k) ans++;
            }
        } 
        return ans;
    }
}

题目要求区间和为k的区间个数，那么利用前缀和优化区间和过程，然后遍历每一个区间，时间复杂度$O(N^2)$。

（2）哈希优化

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        // 初始化的作用，计算长度为1的子数组
        map.put(0,1);
        // 储存preSum[j]
        int preSum = 0;
        int res = 0;
        // 开始遍历储存前缀和
        for (int num : nums) {
            preSum += num;
            // 计算是否存在 preSum[i]
            if (map.containsKey(preSum - k))
                res += map.get(preSum - k);
            // 将这个前缀和存入哈希表
            map.put(preSum, map.getOrDefault(preSum, 0)+1);
        }
        return res;
    }
}

思路分析：求得前缀和之后，问题其实可以归结为：N个数，求差为定值K的数据对个数。

参考两数之和的思路：N个数，从中找和为定值K的数据对。

一个是两数之和，一个是两数之差，但本质无差。我确定两数之中的一个数之后，由于和/差固定，那么就能确定另外一个数的大小。此时，我只需查表来确定另外一个数的出现次数，就能避免重复运算。

---

笔试真题：webank—9.3—笔试第三题_牛客网

这题将数组区间和改为了数组平均值，不过经过算式转化后就变成了和为0的子数组个数。

二维区域和搜索

https://leetcode.cn/problems/range-sum-query-2d-immutable/

class NumMatrix {
    private int[][] preSum; //preSum[i][j] = Sum(matrix[i-1][j-1])

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return;
        preSum = new int[m + 1][n + 1];
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                preSum[i][j] = matrix[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
            }
        }
    }
    
    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];
    }
}

既然有一维的前缀和，那么就有二维的区域和。固定原点为00，那么就能计算从ij到00形成的区域和。

二叉树路径和

https://leetcode.cn/problems/path-sum-iii/description/

（1）普通递归解法

class Solution {
    public int dfs(TreeNode root, long target){
        // 从root开始的结点路径和为target的数量
        if(root==null) return 0;
        int l = dfs(root.left, target-root.val);
        int r = dfs(root.right, target-root.val); 
        int mid = (target==root.val)?1:0;
        return l+r+mid;
    }
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null) return 0;
        return dfs(root, targetSum)+pathSum(root.left, targetSum)+pathSum(root.right, targetSum);
    }
}

用一个dfs计算从根节点到叶子结点上路径和为target的数量。然后再递归计算左右左右子树上符合条件的数量。

这样做有什么缺点？大量重复计算。

重复计算是怎么出现的？不能简化它吗？回顾现在的思路，针对树的一个根结点，计算从根节点开始的路径和。在DFS的过程中，我们的确是节省了计算（从根节点到当前结点），但是一趟DFS结束后，我们转移到了左右子树的根节点，此时计算清空。

换个思路：从下往上。若记当前结点i到根节点root的路径和为$sum(i, root)$，那么从i节点到j结点的路径和可以为表示$sum(i, root)-sum(j,root)$ ，这不正是区间和的简化计算方式吗？

（2）前缀和解法

class Solution {
    int ans =0;
    public void dfs(TreeNode root, Map<Long, Integer> prefixMap, long sum, long targetSum){
        if(root==null) return;
        sum += root.val;
        ans += prefixMap.getOrDefault(sum-targetSum, 0);
        prefixMap.put(sum, prefixMap.getOrDefault(sum, 0)+1);
        dfs(root.left, prefixMap, sum, targetSum); 
        dfs(root.right, prefixMap, sum, targetSum); 
        prefixMap.put(sum, prefixMap.getOrDefault(sum, 0)-1);
    }
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>(); 
        map.put(0L, 1); // for zero prefixSum
        dfs(root, map, 0, targetSum);
        return ans;
    }
}

这里的前缀和就是从当前结点到root结点的路径和。这样二叉树中的一条路径就可以做到O（1）的计算。

注意：

• 我们用Map<Long, Integer>来存储相同前缀和的数量，因为二叉树结点有正有负，可能出现相同前缀和。
• 在结束递归时，减去当前的前缀和。prefixMap.put(sum, prefixMap.getOrDefault(sum, 0)-1); 因为路径不能跨树。

差分

原理介绍

前缀和适用场景：原始数组不被修改的情况下，区间的累加和的频繁查询。

差分技巧适用场景：频繁对原始数组的某个区间的元素进行增减。

（1）原理

给定数组 $A_i$ 则差分数组表示为 $d_i = a_i - a_{i-1}, i=1,2,3,…, d_0=0$

差分抓住了相邻元素间差不变的特性，对一个区间内的所有元素加或减某个数，差分总是不变的。

如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可。

如果你想对区间 nums[i..j] 的元素全部减 3，那么只需要让 diff[i] -= 3，然后再让 diff[j+1] -+ 3 即可。

特别地，如果对整个数组进行加减，只需要对首元素加减即可。

（2）代码实现

1. 构造差分数组

int[] diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

2. 差分数组反推原数组

int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

封装工具类

// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;
    
    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i, j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

航班预订统计

https://leetcode.cn/problems/corporate-flight-bookings/

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n]; // 差分数组
        for(int[] book: bookings){ // 注意下标对齐逻辑
            diff[book[0]-1] += book[2];
            if(book[1]<n)
                diff[book[1]] -= book[2];
        }        
        int[] res = new int[n]; //反推原来数组
        res[0] = diff[0];
        for(int i=1; i<n; ++i){
            res[i] = diff[i] + res[i-1];
        }
        return res;
    }
}

拼车

https://leetcode.cn/problems/car-pooling/description/

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1000];
        for(int[] trip:trips){
            int n = trip[0];
            int l = trip[1];
            int r = trip[2];
            // 上车
            diff[l] += n;
            if(r<1000)
                diff[r] -= n;
        }
        int[] ans = new int[1000];
        ans[0] = diff[0];
        for(int i=1; i<1000; ++i){
           ans[i] = diff[i] + ans[i-1]; 
        }
        for(int num: ans)
            if(num>capacity)
                return false;
        return true;
    }
}

差分数组直观应用，事后检查每公里是否超载。