数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
LeetCode | 力扣 | 难度 |
---|---|---|
303. Range Sum Query - Immutable | 303. 区域和检索 - 数组不可变 | 🟢 |
304. Range Sum Query 2D - Immutable | 304. 二维区域和检索 - 矩阵不可变 | 🟠 |
- | 剑指 Offer II 013. 二维子矩阵的和 | 🟠 |
———–
本文有视频版: 前缀和/差分数组技巧精讲。建议关注我的 B 站账号,我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
先看一道例题,力扣第 303 题「 区域和检索 - 数组不可变」,让你计算数组区间内元素的和,这是一道标准的前缀和问题:
题目要求你实现这样一个类:
class NumArray {
public NumArray(int[] nums) {}
/* 查询闭区间 [left, right] 的累加和 */
public int sumRange(int left, int right) {}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray {
public:
NumArray(vector<int>& nums) {}
/* 查询闭区间 [left, right] 的累加和 */
int sumRange(int left, int right) {}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray:
def __init__(self, nums: List[int]):
pass
# 查询闭区间 [left, right] 的累加和
def sumRange(self, left: int, right: int) -> int:
pass
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NumArray struct {}
func Constructor(nums []int) NumArray {}
// 查询闭区间 [left, right] 的累加和
func (this *NumArray) SumRange(left int, right int) int {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NumArray = function(nums) {
// constructor
this.nums = nums;
// method to sum over range
this.sumRange = function(left, right) {
var sum = 0;
for (var i = left; i <= right; i++) {
sum += nums[i];
}
return sum;
}
/* 查询闭区间 [left, right] 的累加和 */
};
sumRange
函数需要计算并返回一个索引区间之内的元素和,没学过前缀和的人可能写出如下代码:
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int left, int right) {
int res = 0;
for (int i = left; i <= right; i++) {
res += nums[i];
}
return res;
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray {
private:
vector<int> nums;
public:
NumArray(vector<int>& nums) {
this->nums = nums;
}
int sumRange(int left, int right) {
int res = 0;
for (int i = left; i <= right; i++) {
res += nums[i];
}
return res;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
res = 0
for i in range(left, right+1):
res += self.nums[i]
return res
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NumArray struct {
nums []int
}
func Constructor(nums []int) NumArray {
return NumArray{nums: nums}
}
func (this *NumArray) SumRange(left int, right int) int {
res := 0
for i := left; i <= right; i++{
res += this.nums[i]
}
return res
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NumArray = function(nums) {
this.nums = nums;
}
NumArray.prototype.sumRange = function(left, right) {
let res = 0;
for (let i = left; i <= right; i++) {
res += this.nums[i];
}
return res;
}
这样,可以达到效果,但是效率很差,因为 sumRange
方法会被频繁调用,而它的时间复杂度是 O(N)
,其中 N
代表 nums
数组的长度。
这道题的最优解法是使用前缀和技巧,将 sumRange
函数的时间复杂度降为 O(1)
,说白了就是不要在 sumRange
里面用 for 循环,咋整?
直接看代码实现:
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];
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray {
private:
// 前缀和数组
vector<int> preSum;
public:
/* 输入一个数组,构造前缀和 */
NumArray(vector<int>& nums) {
// preSum[0] = 0,便于计算累加和
preSum.resize(nums.size() + 1);
// 计算 nums 的累加和
for (int i = 1; i < preSum.size(); i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumArray:
def __init__(self, nums: List[int]):
# 前缀和数组
self.preSum = [0] * (len(nums) + 1)
# 计算 nums 的累加和
for i in range(1, len(self.preSum)):
self.preSum[i] = self.preSum[i - 1] + nums[i - 1]
def sumRange(self, left: int, right: int) -> int:
# 查询闭区间 [left, right] 的累加和
return self.preSum[right + 1] - self.preSum[left]
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NumArray struct {
// 前缀和数组
preSum []int
}
/* 输入一个数组,构造前缀和 */
func Constructor(nums []int) NumArray {
// preSum[0] = 0,便于计算累加和
n := len(nums)
preSum := make([]int, n + 1)
// 计算 nums 的累加和
for i := 1; i < n + 1; i++ {
preSum[i] = preSum[i - 1] + nums[i - 1]
}
return NumArray{preSum: preSum}
}
/* 查询闭区间 [left, right] 的累加和 */
func (this *NumArray) SumRange(left int, right int) int {
return this.preSum[right + 1] - this.preSum[left]
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NumArray = function(nums) {
// 前缀和数组
this.preSum = new Array(nums.length + 1);
// 计算 nums 的累加和
this.preSum[0] = 0;
for (let i = 1; i < this.preSum.length; i++) {
this.preSum[i] = this.preSum[i - 1] + nums[i - 1];
}
};
// 查询闭区间 [left, right] 的累加和
NumArray.prototype.sumRange = function(left, right) {
return this.preSum[right + 1] - this.preSum[left];
};
核心思路是我们 new 一个新的数组 preSum
出来,preSum[i]
记录 nums[0..i-1]
的累加和,看图 10 = 3 + 5 + 2:
看这个 preSum
数组,如果我想求索引区间 [1, 4]
内的所有元素之和,就可以通过 preSum[5] - preSum[1]
得出。
这样,sumRange
函数仅仅需要做一次减法运算,避免了每次进行 for 循环调用,最坏时间复杂度为常数 O(1)
。
这个技巧在生活中运用也挺广泛的,比方说,你们班上有若干同学,每个同学有一个期末考试的成绩(满分 100 分),那么请你实现一个 API,输入任意一个分数段,返回有多少同学的成绩在这个分数段内。
那么,你可以先通过计数排序的方式计算每个分数具体有多少个同学,然后利用前缀和技巧来实现分数段查询的 API:
int[] scores; // 存储着所有同学的分数
// 试卷满分 100 分
int[] count = new int[100 + 1]
// 记录每个分数有几个同学
for (int score : scores)
count[score]++
// 构造前缀和
for (int i = 1; i < count.length; i++)
count[i] = count[i] + count[i-1];
// 利用 count 这个前缀和数组进行分数段查询
接下来,我们看一看前缀和思路在二维数组中如何运用。
这是力扣第 304 题「 二维区域和检索 - 矩阵不可变」,其实和上一题类似,上一题是让你计算子数组的元素之和,这道题让你计算二维矩阵中子矩阵的元素之和:
比如说输入的 matrix
如下图:
按照题目要求,矩阵左上角为坐标原点 (0, 0)
,那么 sumRegion([2,1,4,3])
就是图中红色的子矩阵,你需要返回该子矩阵的元素和 8。
当然,你可以用一个嵌套 for 循环去遍历这个矩阵,但这样的话 sumRegion
函数的时间复杂度就高了,你算法的格局就低了。
注意任意子矩阵的元素和可以转化成它周边几个大矩阵的元素和的运算:
而这四个大矩阵有一个共同的特点,就是左上角都是 (0, 0)
原点。
那么做这道题更好的思路和一维数组中的前缀和是非常类似的,我们可以维护一个二维 preSum
数组,专门记录以原点为顶点的矩阵的元素之和,就可以用几次加减运算算出任何一个子矩阵的元素和:
class NumMatrix {
// 定义:preSum[i][j] 记录 matrix 中子矩阵 [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];
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumMatrix {
private:
// 定义:preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
vector<vector<int>> preSum;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
if (m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = vector<vector<int>>(m + 1, vector<int>(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] 的元素和
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];
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
class NumMatrix:
# 定义:preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
def __init__(self, matrix: List[List[int]]):
m, n = len(matrix), len(matrix[0])
if m == 0 or n == 0: return
# 构造前缀和矩阵
self.preSum = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
# 计算每个矩阵 [0, 0, i, j] 的元素和
self.preSum[i][j] = self.preSum[i-1][j] + self.preSum[i][j-1] + matrix[i-1][j-1] - self.preSum[i-1][j-1]
# 计算子矩阵 [x1, y1, x2, y2] 的元素和
def sumRegion(self, x1: int, y1: int, x2: int, y2: int) -> int:
# 目标矩阵之和由四个相邻矩阵运算获得
return self.preSum[x2+1][y2+1] - self.preSum[x1][y2+1] - self.preSum[x2+1][y1] + self.preSum[x1][y1]
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
type NumMatrix struct {
// 定义:preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
preSum [][]int
}
func Constructor(matrix [][]int) NumMatrix {
m, n := len(matrix), len(matrix[0])
if m == 0 || n == 0 {
return NumMatrix{}
}
// 构造前缀和矩阵
preSum := make([][]int, m+1)
for i := 0; i <= m; i++ {
preSum[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for 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]
}
}
return NumMatrix{preSum: preSum}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
func (this *NumMatrix) SumRegion(x1 int, y1 int, x2 int, y2 int) int {
// 目标矩阵之和由四个相邻矩阵运算获得
return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1]
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。
var NumMatrix = function(matrix) {
var m = matrix.length, n = matrix[0].length;
if (m === 0 || n === 0) return;
// 构造前缀和矩阵
this.preSum = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0));
for (var i = 1; i <= m; i++) {
for (var j = 1; j <= n; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
this.preSum[i][j] = this.preSum[i-1][j] + this.preSum[i][j-1] + matrix[i - 1][j - 1] - this.preSum[i-1][j-1];
}
}
};
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
NumMatrix.prototype.sumRegion = function(x1, y1, x2, y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1];
};
这样,sumRegion
函数的时间复杂度也用前缀和技巧优化到了 O(1),这是典型的「空间换时间」思路。
前缀和技巧就讲到这里,应该说这个算法技巧是会者不难难者不会,实际运用中还是要多培养自己的思维灵活性,做到一眼看出题目是一个前缀和问题。
除了本文举例的基本用法,前缀和数组经常和其他数据结构或算法技巧相结合,我会在 前缀和技巧高频习题 中举例讲解。
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路:
_____________
《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释