前缀和：区间求和的利器

为什么需要前缀和

暴力求子数组之和：每次查询都要遍历区间，O(n) 每次查询，O(n²) 总时间。

前缀和预处理一次，每次查询 O(1)。

核心思路：

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

区间 [l, r] 的和 = prefix[r+1] - prefix[l]

一维前缀和

模板

int[] buildPrefix(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n + 1];   // 多开一位，prefix[0] = 0
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// 查询 [l, r] 的和（0-indexed）
int query(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

{
  "type": "array-highlight",
  "title": "前缀和构建 nums=[3,1,4,1,5,9]",
  "steps": [
    {
      "note": "初始：prefix=[0, 0, 0, 0, 0, 0, 0]，从 i=0 开始",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 0, 0, 0, 0, 0, 0],
      "highlight": [0],
      "highlight2": [1]
    },
    {
      "note": "prefix[1] = prefix[0] + nums[0] = 0 + 3 = 3",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 0, 0, 0, 0, 0],
      "highlight": [0],
      "highlight2": [1]
    },
    {
      "note": "prefix[2] = prefix[1] + nums[1] = 3 + 1 = 4",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 0, 0, 0, 0],
      "highlight": [1],
      "highlight2": [2]
    },
    {
      "note": "prefix[3] = prefix[2] + nums[2] = 4 + 4 = 8",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 8, 0, 0, 0],
      "highlight": [2],
      "highlight2": [3]
    },
    {
      "note": "构建完成：prefix=[0,3,4,8,9,14,23]。查询 [1,3] = prefix[4]-prefix[1] = 9-3 = 6",
      "array": [3, 1, 4, 1, 5, 9],
      "array2": [0, 3, 4, 8, 9, 14, 23],
      "highlight": [1, 2, 3],
      "highlight2": [1, 4],
      "matched": [1, 2, 3]
    }
  ]
}

区域和检索（LeetCode 303）

class NumArray {
    private int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

前缀和 + 哈希表

当问题变为「和为 k 的子数组个数」，用哈希表记录每个前缀和出现的次数：

核心观察：若 prefix[j] - prefix[i] == k，则 nums[i..j-1] 的和为 k。

等价于：找满足 prefix[i] == prefix[j] - k 的 i 有多少个。

和为 K 的子数组（LeetCode 560）

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);   // 空子数组，前缀和为 0
    int sum = 0, res = 0;
    for (int num : nums) {
        sum += num;
        // 找前面前缀和为 sum-k 的有多少个
        res += count.getOrDefault(sum - k, 0);
        count.merge(sum, 1, Integer::sum);
    }
    return res;
}

连续数组（LeetCode 525）

找最长的子数组使得 0 和 1 个数相等——把 0 变成 -1，问题变为「和为 0 的最长子数组」：

int findMaxLength(int[] nums) {
    Map<Integer, Integer> firstSeen = new HashMap<>();
    firstSeen.put(0, -1);
    int sum = 0, res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0 ? -1 : 1);
        if (firstSeen.containsKey(sum)) {
            res = Math.max(res, i - firstSeen.get(sum));
        } else {
            firstSeen.put(sum, i);  // 只记录第一次出现的位置（找最长）
        }
    }
    return res;
}

二维前缀和

扩展到矩阵：

prefix[i][j] = 左上角 (0,0) 到 (i-1,j-1) 的矩形面积之和

子矩阵 (r1,c1) 到 (r2,c2) 的和：
  = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

二维区域和检索（LeetCode 304）

class NumMatrix {
    private int[][] prefix;

    public 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] = prefix[i-1][j] + prefix[i][j-1]
                    - prefix[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    public 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];
    }
}

对比