【数据结构与算法 | 第五篇】力扣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[x2+1][y2+1] – preSum[x1][y2+1] – preSum[x2+1][y1] + preSum[x1][y1];
}
}

这道题跟前面的类似,但更难理解和实现. 理解背诵:我也晕了… 构建新的,然后新的左上+左上-原左上. 返回+1是跟原先的位置匹配,减去一人一边大的,加全大全小.大的全加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];
}
}