Leetcode-303. Region and retrieval - array immutability (JavaScript)

2021-08-26 20:10:24 Blackn

solution ：

Here we use ` The prefix and ` Solution method

What are prefixes and ？

The prefix and is that we need to create a new array , It's called `preNums`

`preNums[i]` Represents an array `nums` from `0` To `i-1` Of value and

``````nums:       [2, -6,  3, 7, -1]

preNums:[0,  2, -4, -1, 6,  5]
Copy code ``````

`preNums` At initialization time , The first value is 0

`preNums[i]` = `nums[i-1]` + `preNums[i-1]`

Prefix and what can you do ？

The function of prefix and is ： Help us get an array , The sum of the values of any interval

`nums[left]` To `nums[right]` Closed interval Internal value = `preNums[right+1]` - `preNums[left]`

Derivation method

• Array from 0 To left And for `x`
• Array from 0 To right And for `y`
• Array from left To right And for `y - x + nums[left]`
• `nums[left]` = `preNums[left+1]` - `preNums[left]`
• `nums[left]` . . . `nums[right]` = `y - x + nums[left]` = `preNums[right+1]` - `preNums[left+1]` + `nums[left]` = `preNums[right+1]` - `preNums[left]`

This problem is easy to do

First construct prefix and array

And then through `preNums[right+1]` - `preNums[left]` Get the sum in the interval

``````/*
* @lc app=leetcode.cn id=303 lang=javascript
*
* [303]  Area and retrieval  -  The array is immutable
*/

// @lc code=start
/**
* @param {number[]} nums
*/
var NumArray = function (nums) {

//  Construct prefixes and arrays
let preNums = [0]; //  The first value is initialized to  0
for (let i = 1; i <= nums.length; i++) {
preNums[i] = nums[i - 1] + preNums[i - 1];
}
//  take  preNums  Mount to  NumArray  On
this.preNums = preNums;
};

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

/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(left,right)
*/
// @lc code=end
Copy code ``````