3月第一題，LeetCode上區(qū)域和檢索 - 數(shù)組不可變，是構(gòu)建一個類然后通過prototype添加方法，簡單難度，記錄下解題思路
通過傳入的數(shù)組構(gòu)建NumArray類，并且之后調(diào)用NumArray.prototype.sumRange(i,j)方法來計算[i,j]范圍內(nèi)的數(shù)的和
當然可以直接想到：
- 傳入的nums直接賦值給
NumArray類 - 遍歷[i,j]區(qū)間內(nèi)的所有的元素相加，返回結(jié)果即可
var NumArray = function(nums) {
this.arr = nums
};
NumArray.prototype.sumRange = function(i, j) {
// 直接遍歷i,j范圍內(nèi)的所有元素相加并返回
let res = 0
for(let k = i; k<= j;k++) {
res += this.arr[k]
}
return res
};
可以通過測試，正好簡單難度有余力優(yōu)化下題目，接下來試著優(yōu)化
引入前綴和概念
前綴和是一個數(shù)組的某項下標之前(包括此項元素)的所有數(shù)組元素的和。
即presum[i] = nums[i] + nums[i -1] + ....+ nums[0]
那么有了前綴和要如何計算[i,j]區(qū)間的值，假設數(shù)組為[-2,0,3,-5,2,1]，現(xiàn)在求[2,5]之間數(shù)的和
已知對應
index = 5的前綴和presum[5]，那么這里只需要減掉presum[2-1]的前綴和就是最后的結(jié)果，可得結(jié)論sumRange(i,j) = presum[j] - presum[j-1]最后轉(zhuǎn)換為求前綴和數(shù)組
presum，之后根據(jù)傳入的[i,j]查詢計算即可
var NumArray = function (nums) {
// 創(chuàng)建一個前綴和數(shù)組
let preSum = new Array(nums.length + 1);
// 將第一位設為0，會將整體數(shù)組往右移動一位
// 所以preSum[1]對應的是nums[0]的前綴和
preSum[0] = 0;
// 求前綴和
for (let i = 0; i < nums.length; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
this.preSum = preSum;
};
NumArray.prototype.sumRange = function (i, j) {
// 因為右移了一位，所以不是[i-1,j]而是[i,j+1]
return this.preSum[j + 1] - this.preSum[i];
};
優(yōu)化過后可以發(fā)現(xiàn)用時減少很多，并且內(nèi)存消耗也減少了
