前缀和数组:
前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。(仅仅适用于原数组不变的情况,如果原数组经常修改,则需要考虑差分数组。)
模版如下:
class PrefixSum { // 前缀和数组 private int[] preSum; /* 输入一个数组,构造前缀和 */ public PrefixSum(int[] nums) { // preSum[0] = 0,便于计算累加和 preSum = new int[nums.length + 1]; // 计算 nums 的累加和 for (int i = 1; i < preSum.length; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; } } /* 查询闭区间 [left, right] 的累加和 */ public int sumRange(int left, int right) { return preSum[right + 1] - preSum[left]; } }
看两道例题就清楚了:
1. 303. 区域和检索 - 数组不可变 - 力扣(LeetCode)
由于要频繁计算某个区间内的元素之和,暴力解法复杂度太大,显然前缀和比较合适,代码如下:
class NumArray { //前缀和数组 int[] sumArr; public NumArray(int[] nums) { sumArr = new int[nums.length + 1]; for(int i = 1; i < sumArr.length; i++){ sumArr[i] = sumArr[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { //计算[i, j]范围内的和是用sumArr[j + 1] - sumArr[i]计算 return sumArr[right + 1] - sumArr[left]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */
2. 304. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode)
这道题将前缀和数组扩展到了二维:
在构建前缀和数组时,可以定义前缀和数组(i, j)的值为原矩阵到由(0, 0)到(i - 1, j - 1)构成的子矩阵内部的元素之和,任意矩阵都可以由几个子矩阵的加减运算得到,原理如下图:
代码如下:
class NumMatrix { int[][] sumArr; public NumMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; sumArr = new int[m + 1][n + 1]; //初始化前缀和数组 for(int i = 1; i < m + 1; i++){ for(int j = 1; j < n + 1; j++){ sumArr[i][j] = sumArr[i][j - 1] + sumArr[i - 1][j] + matrix[i - 1][j - 1] - sumArr[i - 1][j - 1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { // System.out.println("------"); // for(int[] row : sumArr){ // System.out.println(Arrays.toString(row)); // } return sumArr[row2 + 1][col2 + 1] - (sumArr[row2 + 1][col1] + sumArr[row1][col2 + 1] - sumArr[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); */
class NumArray { //前缀和数组 int[] sumArr;
public NumArray(int[] nums) { sumArr = new int[nums.length + 1]; for(int i = 1; i < sumArr.length; i++){ sumArr[i] = sumArr[i - 1] + nums[i - 1]; } } public int sumRange(int left, int right) { //计算[i, j]范围内的和是用sumArr[j + 1] - sumArr[i]计算 return sumArr[right + 1] - sumArr[left]; } }
/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */ 标签:sumArr,前缀,nums,int,NumArray,差分,数组,leetcode From: https://www.cnblogs.com/xkge/p/17505271.html