【数据结构与算法 | 第五篇】力扣303,304前缀和数组

力扣 303. 区域和检索 - 数组不可变。用法本质:就是新创建一个数组,大小多1.然后数组的值是原数组与前面的和.这样用新数组-前面数组就行了.class NumArray { // 前缀和数组 private int[] preSum; // 输入一个数组构造前缀和 public NumArray(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]; } }题目要求我们来收集数组索引[left,right]之间的所有值思路:new一个新数组,用来存储数组当前以及前面之和,最后就可以用这个数组来后-前得到注意:new出来的数组大小要1,因为防止当0-1越界于是preSum[i]的含义变成了nums 前 i 个元素的和preSum[0]0表示前 0 个元素的和。力扣第 304 题「二维区域和检索 - 矩阵不可变class NumMatrix { // preSum[i][j] 记录矩阵 [0, 0, i-1, j-1] 的元素和 private int[][] preSum; public NumMatrix(int[][] matrix) { int m matrix.length, n matrix[0].length; if (m 0 || n 0) return; // 构造前缀和矩阵 preSum new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { // 计算每个矩阵 [0, 0, i, j] 的元素和 preSum[i][j] preSum[i-1][j] preSum[i][j-1] matrix[i - 1][j - 1] - preSum[i-1][j-1]; } } } // 计算子矩阵 [x1, y1, x2, y2] 的元素和 public int sumRegion(int x1, int y1, int x2, int y2) { // 目标矩阵之和由四个相邻矩阵运算获得 return preSum[x21][y21] - preSum[x1][y21] - preSum[x21][y1] preSum[x1][y1]; } }这道题跟前面的类似,但更难理解和实现.理解背诵:我也晕了…构建新的,然后新的左上左上-原左上.返回1是跟原先的位置匹配,减去一人一边大的,加全大全小.大的全加1代码模版:classNumArray{// 前缀和数组privateint[]preSum;// 输入一个数组构造前缀和publicNumArray(int[]nums){// preSum[0] 0便于计算累加和preSumnewint[nums.length1];// 计算 nums 的累加和for(inti1;ipreSum.length;i){preSum[i]preSum[i-1]nums[i-1];}}// 查询闭区间 [left, right] 的累加和publicintsumRange(intleft,intright){returnpreSum[right1]-preSum[left];}}