参阅基础

简介

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

相关习题

Leetcode 303. 区域和检索 - 数组不可变 (实例题)

题目

比方说，你们班上有若干同学，每个同学有一个期末考试的成绩（满分 100 分），那么请你实现一个 API，输入任意一个分数段，返回有多少同学的成绩在这个分数段内。

我的题解

核心思路：根据一维数组的前缀和求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 同学成绩
let scores = [80, 90, 80, 60, 65, 70, 68, 50, 40, 100, 38, 17];

/* 6-16行只在前缀和数组解法中使用 */

// 试卷满分100分 (0-100)
const count = new Array(101);
count.fill(0);

scores.forEach((score) => {
	count[score]++;
});

for (let index = 1; index < count.length; index++) {
	count[index] = count[index] + count[index - 1];
}

// 判断区间内的同学人数（请输入分数的）
const sumStudent = (scoreA, scoreB) => {
	[scoreA, scoreB] = standardInput(scoreA, scoreB);

    // 暴力解 1
    // return scores.filter((score) => score <= scoreB && score >= scoreA)
    //   .length;

    // 前缀和数组解 2
    return count[scoreB] - count[scoreA - 1 < 0 ? 0 : scoreA - 1];
};

// 防止用户输入的第一个值比第二个值大
const standardInput = (a, b) => {
	return [a, b].sort((a, b) => a - b);
};

const standardStudentLen = sumStudent(60, 100);
console.log("score in 60-100 students: " + standardStudentLen);

LeetCode 304. 二维区域和检索 - 矩阵不可变

题目

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

来源：304. 二维区域和检索 - 矩阵不可变

我的题解

核心思路：根据一维数组的前缀和求解（二维目前还没看）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class NumMatrix {
    constructor(matrix) {
        this.matrix = matrix;
        this.NumMatrix();
    }

    NumMatrix() {
    	for (let i = 0; i <= this.matrix.length - 1; i++) {
    		for (let j = 0; j <= this.matrix[i].length - 1; j++) {
    			if (j !== 0) {
    				this.matrix[i][j] = this.matrix[i][j] + this.matrix[i][j - 1];
    			}
    		}
		}
	}

	sumArrRange([row1, col1, row2, col2]) {
		let sum = 0;

		if (col1 === 0) {
			for (let i = row1; i <= row2; i++) {
				sum += this.matrix[i][col2];
			}
		} else {
			for (let i = row1; i <= row2; i++) {
				sum += this.matrix[i][col2] - this.matrix[i][col1 - 1];
			}
		}

		return sum;
	}
}

let matrix = [
    [1, 2, 3, 4, 5],
    [5, 6, 9, 8, 7],
    [0, 1, 2, 3, 4],
    [1, 5, 8, 1, 4],
    [0, 8, 5, 9, 10],
];

const numMatrix = new NumMatrix(matrix);

console.log(numMatrix.sumArrRange([0, 0, 4, 4]));//111