前缀和数组

用于求出数组中索引区间元素和

题目

一维数组前缀和

Leetcode303：区域和检索-数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

1 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
最多调用 104 次 sumRange 方法

实现代码

class NumArray {

  int[] sum;

  public NumArray(int[] nums) {

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

  public int sumRange(int left, int right) {

    return sum[right + 1] - sum[left];
  }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */

解题思路

通过构建一个新数组，存储0索引位置到指定索引位置区间元素的和，如：

PixPin_2025-11-07_21-49-38

数组B用于存储数组A从索引0到索引n区间的元素和，如数组B索引2 = 数组A索引0 + 数组A索引1，求索引区间元素和则是：

数组A[left -> right] = 数组B[right + 1] - 数组B[left]

注意：构建元素和的数组必须要比原数组大小多1

假设数组A和数组B相同长度，如下：

PixPin_2025-11-07_21-58-41

区间范围元素和：

数组A[left -> right] = 数组B[right] - 数组B[left - 1]

那么如果是求数组A索引区间0到开始的元素和，就需要判断边界值

时间复杂度

时间组成：

假设nums长度为n

构建前缀和，遍历nums数组：O(n)
计算区间和：O(1)

总的时间：题目的目的是计算索引范围和，所以构造前缀和的时间不算进来，因此时间复杂度为O(1)

空间复杂度

空间组成：

存储元素区间和的数组sum：O(n + 1)

总的空间：O(n)

二维数组前缀和

Leetcode304：二维区域和检索-矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

实现代码

有两种解法：

当做一维数组前缀和处理，遍历每行，进行相加；

构建一个二维数组前缀和；

第一种方式的时间复杂度为O(n)，但是第二种为O(1)，所以下面使用第二种来讲解；

class NumMatrix {

  int[][] matrixSum;

  public NumMatrix(int[][] matrix) {

    int xLen = matrix.length;
    int yLen = matrix[0].length;
    // 思路：二维前缀和，先构建matrixSum
    matrixSum = new int[xLen + 1][yLen + 1];
    // 公式：matrixSum[i+1,j+1] = matrixSum[i,j+1] + matrixSum[i+1,j] - matrixSum[i,j] + matrix[i,j]
    for (int i = 0; i < xLen; i++) {
      for (int j = 0; j < yLen; j++) {
        matrixSum[i + 1][j + 1] = matrixSum[i][j + 1] + matrixSum[i + 1][j] - matrixSum[i][j] + matrix[i][j];
      }
    }

  }

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

  }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */