3月第一题，LeetCode上区域和检索 - 数组不可变，是构建一个类然后通过prototype添加方法，简单难度，记录下解题思路

通过传入的数组构建NumArray类，并且之后调用NumArray.prototype.sumRange(i,j)方法来计算[i,j]范围内的数的和

当然可以直接想到：

1. 传入的nums直接赋值给NumArray类
2. 遍历[i,j]区间内的所有的元素相加，返回结果即可

var NumArray = function(nums) {
  this.arr = nums
};
NumArray.prototype.sumRange = function(i, j) {
    // 直接遍历i,j范围内的所有元素相加并返回
    let res = 0
    for(let k = i; k<= j;k++) {
      res  += this.arr[k]
    }
    return res
};

可以通过测试，正好简单难度有余力优化下题目，接下来试着优化

引入前缀和概念

前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。
即presum[i] = nums[i] + nums[i -1] + ....+ nums[0]

那么有了前缀和要如何计算[i,j]区间的值，假设数组为[-2,0,3,-5,2,1]，现在求[2,5]之间数的和

var NumArray = function (nums) {
    // 创建一个前缀和数组
    let preSum = new Array(nums.length + 1);
    // 将第一位设为0，会将整体数组往右移动一位
    // 所以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];
};

优化过后可以发现用时减少很多，并且内存消耗也减少了