current position:Home>Leetcode-303. Region and retrieval - array immutability (JavaScript)

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

2021-08-26 20:10:24 Blackn

Topic link :leetcode-cn.com/problems/ra…

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/72f1b79e6810481db7c9c056bc261435~tplv-k3u1fbpfcp-zoom-1.image

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 

copyright notice
author[Blackn],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210826201021679z.html

Random recommended