| 题目 | 难度 | 要点 |
|---|---|---|
| 区域和检索 - 数组不可变 | ● | 构造前缀和数组，避免每次O(n)遍历统计区间和 |
| 二维区域和检索 - 矩阵不可变 | ● | 矩阵前缀和，并通过矩阵加减拼凑目标矩阵 |
区域和检索 - 数组不可变
class NumArray {
private 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];
}
}
二维区域和检索 - 矩阵不可变