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

Solution:

Here we use the prefix sum

What is prefix sum?

The prefix and the sum are we need to create a new array called preNums

PreNums [I] represents the sum of the values of the array nums from 0 to i-1

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

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

PreNums is initialized with the first value 0

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

What does prefix sum do?

And that’s what it does: it helps us get the sum of any range of values in an array

PreNums [left] = preNums[right] -prenums [left]

Derivation method

  • The sum from 0 to left is 0x
  • The sum from 0 to right is 0y
  • The sum from left to right isy - 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]

So this is pretty easy to do

Start by constructing prefixes and arrays

PreNums [right+1] -prenums [left

// @lc code=start /** * @param {number[]} Var NumArray = function (nums) {let preNums = [0]; // initialize the first value to 0 for (let I = 1; i <= nums.length; i++) { preNums[i] = nums[i - 1] + preNums[i - 1]; } 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=endCopy the code