跳到主要内容

前缀和与差分

问题​

前缀和与差分数组的原理和常见题目有哪些？

答案​

一维前缀和​

前缀和数组构建与区间查询
// 原数组: nums = [1, 2, 3, 4, 5]
// 前缀和: prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
// prefix = [0, 1, 3, 6, 10, 15]
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// 区间 [l, r] 的和 = prefix[r+1] - prefix[l]，O(1) 查询
int rangeSum = prefix[r + 1] - prefix[l];

二维前缀和（LeetCode 304）​

二维矩阵区域和
class NumMatrix {
    int[][] prefix;
    
    NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] 
                    + prefix[i][j-1] - prefix[i-1][j-1];
            }
        }
    }
    
    // 查询 (r1,c1) 到 (r2,c2) 区域和
    int sumRegion(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] - prefix[r1][c2+1] 
            - prefix[r2+1][c1] + prefix[r1][c1];
    }
}

差分数组​

差分数组：区间加操作 O(1)
// 对 [l, r] 区间每个元素加 val
int[] diff = new int[n];
diff[l] += val;
if (r + 1 < n) diff[r + 1] -= val;

// 还原数组：前缀和
int[] result = new int[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
    result[i] = result[i - 1] + diff[i];
}

航班预订统计（LeetCode 1109）​

差分数组经典应用
public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n];
    for (int[] b : bookings) {
        diff[b[0] - 1] += b[2];                // 起点加
        if (b[1] < n) diff[b[1]] -= b[2];       // 终点+1 减
    }
    // 前缀和还原
    for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
    return diff;
}

和为 K 的子数组（LeetCode 560）​

前缀和 + HashMap
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        count += map.getOrDefault(sum - k, 0);
        map.merge(sum, 1, Integer::sum);
    }
    return count;
}
前缀和 vs 差分
  • 前缀和：预处理后 O(1)O(1) 查询区间和
  • 差分：O(1)O(1) 区间修改，最后前缀和还原
  • 互为逆运算：前缀和的差分 = 原数组，差分的前缀和 = 原数组

常见面试问题​

Q1: 前缀和的适用场景？​

答案：

多次查询区间和、查找和为 K 的子数组数量、二维区域和查询。核心是空间换时间：O(n)O(n) 预处理，O(1)O(1) 查询。

Q2: 差分数组的适用场景？​

答案：

多次区间加减操作：如航班预订、公交上下车、拼车问题。O(1)O(1) 修改，最后 O(n)O(n) 还原。

相关链接​