【小f的刷题笔记】（JS）数组 - 前缀和 LeetCode303 & LeetCode34

【数组】

前缀和：

🌟 原始数组不会被修改的情况下，频繁查询某个区间的累加和

✔ 一次把所有从一开始到本数的累加值计算出来存在一个新数组里，区间的累加值通过减法得出

---

LeetCode303

链接：

303.区域和检索 - 数组不可变

题目：

思路：

-> 就是利用前缀和，不用让代码每一个都遍历一次，直接后减前就行

这题不一样的点在于是去实现一个类，所以定义的是类的方法，和普通声明函数有些许区别的

注意点：

1️⃣ js在定义一个函数之后，同时也得到了一个同名的类，这里的NumArray也是作为了一个类

2️⃣ js中类的方法都存在原型中，要修改类的原型就得用通过类.prototype属性去修改

3️⃣ 方法中的this代表的是实例化后的对象

代码：

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.sums = new Array(nums.length+1).fill(0);
    for(let i=0; i<nums.length; i++) {
        // 从1开始的
        this.sums[i+1] = this.sums[i] + nums[i];
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    return this.sums[right+1] - this.sums[left];
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */
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

---

LeetCode34

链接：

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

题目：

思路：

这道题和上面那道真是一模一样，只是变成二维的了，不能简单的后减前，要通过几块的和加加减减才能出来

代码：

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    const m = matrix.length;
    if(m>0) {
        const n = matrix[0].length;
        // 建立初值全为0的二维数组
        this.sums = new Array(m+1).fill(0).map(()=> new Array(n+1).fill(0));
        for(let i=0; i<m; i++) {
            for(let j=0; j<n; j++) {
                this.sums[i+1][j+1] = this.sums[i][j+1] + this.sums[i+1][j] - this.sums[i][j] + matrix[i][j];
            }
        }
    }
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + this.sums[row1][col1];
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */
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

---

JS知识点：

👇 建立初值全为0的二维数组

this.sums = new Array(m+1).fill(0).map(()=> new Array(n+1).fill(0));

---

写在最后：
开始跟着labuladong的算法秘籍开始刷题啦
因为要走前端，用js刷题会比较好，C++可能就不大合适了
第一次尝试用js刷题，也一边在恶补js，有些内置方法没用得很熟练，加油啦！