The author of this blog works with CSDN
Tank_in_the_streetThe author is the same author, reprint the article need to indicate the source, thank you for your cooperation.
study hard and make progress every day However, the front end of algorithm and data structure is not a good front end. In order to improve my ability, MY younger brother started to get into the trouble of leetcode, so as to provide more ability foundation for future promotion, salary increase or job-hopping.
So without further ado, let’s start problem one of Leetcode, and before we go to problem one, let’s look at the problem.
Find two numbers in an array and return their subscripts if they add up to the target value. The premise here is that these two numbers can’t have the same subscripts. One solution that many of you might have thought of after knowing this is the double for loop violence solution. However, this method sacrifices time to solve the problem, and the time complexity is N squared. Personally, SINCE we have done the algorithm, we must optimize the time. So the first thing I do is I pass the value of the array into an object as a property of that object, and the property of that object is the index of the value of the array. Then the array is iterated. If the new value of the target minus the value of the current array exists in the object and the current subscript is not equal to the property value of the object where the new value resides, the two subscripts are found. The key codes are as follows:
The final result is that the time complexity is N. However, after this problem is passed, I wonder if I have sacrificed a little space for the optimization of time in this problem. Is there a way to optimize time without sacrificing too much space? Taking a look at the fastest method in leetCode, the 56ms code looks like this:
However, this approach is to sacrifice time for space. The in in judgment is actually the JavaScript engine traverses the object once, so I think the actual time complexity of this method is also n square, and I also run it myself. The result is like this:
But the last 60ms is the real optimization of the algorithm without sacrificing space and using a layer of for loop:
Running it on my own is actually more spatially optimized than my current algorithm:
Then I thought about the algorithm, and it judged one less index than I did because its object attributes are added at the end of each iteration, instead of storing all obj attributes in a for loop like I did. The nice thing about this method is that the for loop is at worst iterated, at best it breaks out of the loop after the second iteration, and there aren’t too many properties in OBJ. Mine, by storing all the attributes for OBj in the first place, is at best or at worst going through one more array than he does. Since I have all the property values in my object, I also need to determine once if the current index is duplicated.