Topic describes

Title from Leetcode 303. Fields and retrievals – Arrays are immutable

Given an integer array nums, find the sum of the elements in the range from index I to j (I ≤ j), including I and j.

Implement NumArray class:

  • NumArray(int[] nums)Use an arraynumsInitialize an object
  • toJ (I ≤ j)The sum of elements in the range, containingi,jTwo points (i.esum(nums[i].nums[i + 1]. .nums[j]))

Example:

Input:"NumArray"."sumRange"."sumRange"."sumRange"[[[...2.0.3, -5.2, -1]], [0.2], [2.5], [0.5] output: [null.1, -1, -3NumArray NumArray =new NumArray([-2.0.3, -5.2, -1]);
numArray.sumRange(0.2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2.5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0.5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
Copy the code

Tip:

  • 0 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= i <= j < nums.length
  • Most call10 ^ 4 次 sumRangemethods

Thought analysis

So this is a very simple problem, and the first thing that we might think of is to iterate over the sumRange. But take a closer look at the hints? Boy! If we’re going to call the method 10^4 times, that means we’re going to have to reevaluate a lot of values.

Therefore, we came up with the idea of optimizing (caching) the process with prefix summing — iterating over the statistics prefix summing during reinitialization.

What about further optimizations? In fact, we can postpone the calculation of prefix sums until we need to.

Topic answer

/ * * *@param {number[]} nums* /
var NumArray = function (nums) {
    let sums = [0];
    nums.forEach((num, i) = > {
        sums.push(sums[i] + nums[i]);
    })
    this.sums = sums;
};

/ * * *@param {number} i 
 * @param {number} j
 * @return {number}* /
NumArray.prototype.sumRange = function (i, j) {
    return this.sums[j + 1] - this.sums[i];
};
Copy the code
/ * * *@param {number[]} nums* /
var NumArray = function (nums) {
    this.sums = [0];
    this.nums = nums;
};

/ * * *@param {number} i 
 * @param {number} j
 * @return {number}* /
NumArray.prototype.sumRange = function (i, j) {
    let k = this.sums.length - 1;
    while (k <= j) {
        this.sums.push(this.sums[k] + this.nums[k]);
        k++;
    }
    return this.sums[j + 1] - this.sums[i];
};
Copy the code

conclusion

The solution to this problem mainly uses the idea of prefixes and sums. Also, we note that there is a trick here, to ensure the sums(I, j), I > 0 and sums(0, j) calculations are uniform, we store a placeholder 0 in sum[0].

Today’s daily punch card is over ~ haven’t written the question for a long time, first find the feeling ~