In order to prepare for the school admission, I also started to brush some algorithm problems on Leetcode in the past two months. From the beginning, Eay depends on the solution of the problem. Now I can beat most medium by myself, and occasionally I can beat hard. I feel that there is some progress. I also opened a JavaScript writing algorithm on GitHub repo, front-end partners can be a field oh!

GitHub link: LeetCode-JavaScript

Topic describes

Leetcode Link: 303 Area and Retrieval – Array immutable (Easy)

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) Initializes an object using the array nums
  • Int sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) sumRange(int I, int j) The 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 <= 104
  • -105 <= nums[i] <= 105
  • 0 <= i <= j < nums.length
  • Call the sumRange method up to 104 times

JavaScript template:

/ * * *@param {number[]} nums* /
var NumArray = function(nums) {};/ * * *@param {number} i 
 * @param {number} j
 * @return {number}* /
NumArray.prototype.sumRange = function(i, j) {};/** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(i,j) */
Copy the code

Thought analysis

At first glance, I thought it was complicated because of this strange example, but a closer look will show that it is indeed easy. M: No, it’s very easy. There are only two steps we need to complete:

  1. Use NumArray to initialize a NUMS array. I didn’t really think there was any deep meaning behind this step and just added an array property representing the NUMS array. The time complexity is O(1) :
var NumArray = function(nums) {
  this.array = nums;
};
Copy the code
  1. Returns the sum of the elements in the range when the sumRange method is called. This step is not difficult at first glance, so I define a sum method with reduce, which is called in O(n) time:
NumArray.prototype.sumRange = function(i, j) {
  return this.array.slice(i,j+1).reduce((a,b) = > a+b);
};
Copy the code

And then… And then there was no…! I read the topic again, and found that there was really no other demand, so I submitted it with anxiety. Unexpectedly, unexpectedly, the solution that only took two minutes was passed once:

Wait, what about this execution time –!

To optimize the

And it didn’t take me long to figure out this time-consuming problem, which is the sum of O(n) time, so what can we do to reduce the complexity? I found that in the initialization part, we could actually do a few more things to make the query part easier:

We can maintain an array of prefixes and instead of the array itself during initialization, and the initialization time becomes O(n) :

var NumArray = function(nums) {
  let length = nums.length;
  this.preSum = new Array(length + 1).fill(0); // Initialize the prefix and array
  for (let i = 0; i < length; i++) {
    this.preSum[i+1] = this.preSum[i] + nums[i]; // Assign a value to an element}};Copy the code

However, in the query, we only need to calculate the difference between the prefix sum of j+1 and I, so the time complexity becomes O(1) :

NumArray.prototype.sumRange = function(i, j) {
  return this.preSum\[j+1\] - this.preSum\[i\];
};
Copy the code

So we get a normal time complexity ψ(‘ ∇´)

To summarize

We managed to reduce the time complexity of the query from O(n) to O(1) by doing more operations at initialization. But all in all, this is a very easy problem.

However, with respect to the virtue of LeetCode, the water in the first question of this month means that the following questions will be difficult. I hope there will not be any questions that will kill me on the way to punch the card. March, go!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign