力扣labuladong——一刷day19

力扣labuladong——一刷day19"/>

力扣labuladong——一刷day19

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、力扣303. 区域和检索 - 数组不可变
• 二、力扣304. 二维区域和检索 - 矩阵不可变

前言

巧用前缀和
前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和

一、力扣303. 区域和检索 - 数组不可变

class NumArray {int[] preSum;public NumArray(int[] nums) {preSum = new int[nums.length+1];for(int i = 1; i < preSum.length;i ++){preSum[i] = preSum[i-1] + nums[i-1];}}public int sumRange(int left, int right) {return preSum[right+1] - preSum[left];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/

二、力扣304. 二维区域和检索 - 矩阵不可变

class NumMatrix {int[][] preSum;public NumMatrix(int[][] matrix) {preSum = new int[matrix.length+1][matrix[0].length+1];for(int i = 1; i < preSum.length; i ++){for(int j = 1; j < preSum[0].length; j ++){preSum[i][j] = matrix[i-1][j-1] + preSum[i][j-1] + preSum[i-1][j] - preSum[i-1][j-1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return preSum[row2+1][col2+1] - preSum[row1][col2+1]- preSum[row2+1][col1] + preSum[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);*/