Name: アルゴリズムの解き方 - 2 つの和 (How To Solve Algorithms - Two Sum)
Uploaded: 2021-01-14T10:21:03.000Z
Duration: 6 min 56 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

動名詞

are you trying to apply for a job but keep getting stuck trying to solve stupid algorithms over and over again?

最上級形容詞

We'll no longer is this going to be a problem, because in today's video, I'm going to go over the to some algorithm and show you the most efficient way to solve the problem.

命令形

Some algorithm is a great algorithm to get started with, because the answer to the solution is really easy to come by.

But that obvious answer is definitely not the most efficient.

There is a more efficient and more complex answer to this problem, which, once you understand, it really opens your eyes to thinking about these algorithms in a different light than just trying to brute force it in the easiest way possible.

It's also not too difficult to come across this less obvious answer, which is why it's a great starting place for anyone looking to learn more algorithms.

Let's go through what the algorithm is asking us to do it, saying that given an array of images so numbers we want to return the indices of those numbers in Saudi array such that those two numbers that we return add up to a specific target number we're asking for.

Also, it says that we can assume that there's exactly one solution for every single array.

So we don't have to worry about returning multiple different oh, answers to the problem.

There's only ever two numbers and the ray that add up to the target.

So, for example, given the numbers to 7 11 and 15 we want to find which in disease in Monterey add up to the target number of nine.

And in our case, this is going to be the number of the Indus zero and the number at the index one in our case, two and seven.

So we were to turn an array of zero and one, and that would be the answer to the problem.

So if we jump over to the white board here, we can kind of see our basic initial algorithm written out.

We have our array of images, which is our numbers and also the target, which is the energy we want to add up to.

And, of course, we want to return the indices of the two numbers that ad together to make that target.

So the naive approach of the initial approach, which is not the most efficient, is to first we have here a loop going over all of our numbers.

So we get our number and index for each of the numbers in are given a ray up here.

And then we looked through that number array again a second time, and we want to check to see if our two numbers here number plus number two, which is from our second loop of the array, add up to equal that target.

And if they do, then we return both of those indexes inside of an array, and this works 100% of the time and our code 100% execute.

But the problem is, as we have a loop inside of another loop, which means we have to run through this number's array once for every single number inside the numbers array, which means it's a big o notation of end squared, which is really bad.

It's really slow, and as the array gets larger and larger, this method is going to become exponentially slower.

So what we want to do is We want to go through this array of numbers only one time instead of going through it twice, as you can see here, which essentially means we want 14 loop and not multiple four loops.

And in order to do that, we need to keep track of all the numbers that we've already looked at and what numbers we need.

So here I have our new algorithm and it starts out very similar to our previous algorithm.

We're looping through all the different numbers in our ray get in the number and the index, but there is no other four lives inside of here.

The way that we're calculating if we've encountered the numbers that we need is we're using this previous values variable here to store all the previous values that we've encountered to see if we have already encountered the value that adds up to make the target.

If you look down here ways you see first we're getting the number that we need right here.

We're getting the needed value vice, attracting the current number from the target, and that's what other number we need to add up to make this number, then inside of our previous values.

Have we encountered that needed value before?

And if we have, we're going to get index here.

So if that index exist, we know that we have both the indexes we need in order to solve this problem.

But if that in dice does not already exist, what we do is restore that number as the key of our hash.

And then the value of that hash is going to be the index where that number took place.

So essentially, we're just restoring our ray inside of a hash, which means we can look up the number instantly without having to look through our entire ray every single time to see if the number exist.

So now that we have a high level understanding of this algorithm, let's go ahead and implement this using Java script to get started programming this, we need to first create that previous values hash that we have.

So we just said that to an empty object, and then we want to look through all of our different numbers.

I'm just going to use a traditional for a loop here so we can say we have a variable I we want initialize as zero And then what we want to do is we wanna say when I is less than our numbers dot length What we want to do is add one toe I every single time and inside of here we can do all of the code for checking our values.

So the first thing that we want to do is we want to get the value that we need so we can create a variable called needed value.

We can set that equal to our target minus our current number, which we also should probably set to variable so we can say our current number.

I was just going to be equal to numbs with the index of I and down here we can use that current number just like that.

It's going to be our needed value and we can check to see if we have an index that is equal to that.

So we'll just set this equal to be index to is going to be equal to previous values.

And we're going to check the object to see if it has something for the key of needed value.

Make sure I spell that correctly and there we go and the next thing we could do is our actual.

If so, we can save index to index to is not equal to know.

Then that means that we have something for that object and we can return it down here.

So we just want to say Return index to an index and that's all perfect.

And now in case, for example, we don't have anything for Index.

Do we want to save that so we can take our previous values that we have?

We can take our current number and we, of course, just want to store the index for that current number, which in our case, is I make sure I change this toe I and that should be everything we need to do to get this working.

So let's click run code down here and it's running and you see that it finished.

Our output was exactly what we're expecting to get, so that's perfect.

It's judging right now, and if we look over here, we can see that we got a success Are run time with 72 most seconds, which is quite a bit faster in the most of the other submissions, which is really great.

Also, the memory footprint was a little bit less, which is also really good.

And if we would have done this the slower way with the double for loop, you'll know that this run time would have been a lot slower here.

And that's how you solve the to some algorithm if you enjoyed it.

Down in the comments below, I enjoyed making this video a lot.

And I'd love to make other videos like this in the future.

But I need you to let me know you're enjoying it, so I know to make more videos.

Also, when you're going about solving your own algorithms, I highly recommend the whiteboard method because it makes solving the algorithms so much easier.

 And with that other way, thank you all very much for watching this video. 

字幕リスト動画再生

アルゴリズムの解き方 - 2 つの和 (How To Solve Algorithms - Two Sum)

stick

essentially

assume

approach