So today let's solve contains duplicate.

だから今日は、重複を解決しよう。

This is another problem from the blind 75 list of questions we've been working on.

これも、私たちが取り組んできたブラインド75の問題リストの中の1つだ。

So I like this problem because it's a good problem for beginners, but there's also multiple solutions to it that I'd like to go over in this video.

この問題は初心者にとって良い問題なので気に入っているのですが、このビデオでは複数の解決策も紹介したいと思います。

So we're given an array of numbers.

つまり、数字の配列が与えられている。

We want to return true if there's any value in that list of numbers that appears at least twice, but maybe it could appear three times or four times, right?

その数字のリストの中に、少なくとも2回、もしかしたら3回、4回出てくる値があればtrueを返したいんだ。

Just at least twice, and we want to return false.

少なくとも2回、falseを返したい。

If there aren't any values that appear at least twice, basically what that means is that every value in the array is distinct.

少なくとも2回出現する値がない場合、基本的にそれは配列のすべての値が明確であることを意味する。

So let's take a look at an example.

では、例を見てみよう。

We have one, two, three, and then we have one again.

1本、2本、3本、そしてまた1本。

So of course this has duplicates, right?

ということは、もちろん重複があるわけだよね？

So we return true.

だから我々は真を返す。

And the easiest way we would be able to detect that is by brute forcing this.

それを検知する最も簡単な方法は、ブルートフォース（総当たり）だ。

So given these numbers, the first thing we do is look at the first number.

これらの数字が与えられたら、まず最初の数字を見る。

It's one.

それは一つだ。

How do we know if this is a duplicate or not?

重複しているかどうか、どうすればわかるのか？

Well, we'd have to compare it to every single number in the rest of the array.

まあ、配列の残りのすべての数字と比較しなければならない。

So that would be a big O of n time operation just to check if the first number is a duplicate or not.

そのため、最初の数字が重複しているかどうかをチェックするだけで、n乗の大きな演算が必要となる。

And then we'd have to do that for every number.

そして、すべての数字に対してそれをしなければならない。

Then we have to check, is the second number a duplicate?

次に、2番目の番号が重複していないかどうかをチェックする必要がある。

How do we know?

なぜわかるのか？

We have to compare it to every other number.

他のすべての数字と比較しなければならない。

We do the same thing with the third one and the last one.

3本目も最後の1本も同じことをする。

And so since we're doing it for every number in the array, the overall time complexity is going to become n squared.

そして、配列内のすべての数値に対してこれを行うので、全体的な時間の複雑さはn乗になる。

And by the way, in this case, n is just the size of the input array.

ちなみにこの場合、nは単なる入力配列のサイズである。

So the brute force solution is big O n squared time complexity.

そのため、総当りによる解は、時間複雑度がO n乗となる。

But the good thing is we don't need any extra memory.

しかし、良いことは、余分なメモリーを必要としないことだ。

So the memory complexity is big O of one.

そのため、メモリの複雑さは1つの大きなOとなる。

It's definitely not a bad solution, but the question is, can we do better than that?

悪い解決策ではないのは確かだが、問題はそれ以上のものができるかどうかだ。

And yes, we definitely can.

そして、そうだ。

A second approach that will help us is sorting.

私たちを助けてくれる2つ目のアプローチは、ソーティングである。

What happens if we took this array and we sorted it?

この配列をソートしたらどうなるだろう？

It would look a little bit different.

少し違って見えるだろう。

It would look like this.

こんな感じだ。

Okay.

オーケー。

But how does sorting help us?

しかし、仕分けが私たちにどのように役立つのだろうか？

Well, let's think about it.

まあ、考えてみよう。

If we sort the input, then any duplicates that do exist in the array, and clearly we see that two duplicates exist at the beginning of the array, they're going to be adjacent.

入力を並べ替えると、配列の中に重複が存在する場合、そして明らかに配列の最初に2つの重複が存在する場合、それらは隣接することになる。

So when we're trying to detect any duplicates in here, we only have to iterate through the array once.

つまり、重複を検出しようとする場合、配列を一度だけ繰り返し処理すればいいのだ。

And as we do that, we're just going to be comparing two neighbors in the array, checking if they're duplicates.

その際、配列内の2つの隣同士を比較し、重複しているかどうかをチェックする。

Next, we're going to shift our pointers to the next spot.

次に、ポインターを次の場所に移す。

Are these duplicates, are these duplicates, et cetera, et cetera, until we finish the entire array.

重複していないか、重複していないか、などなど、配列全体が終わるまで。

In this case, we see that these two adjacent values are duplicates, so we can return true.

この場合、隣接する2つの値は重複していることがわかるので、trueを返すことができる。

And what's the time complexity of this?

この時間の複雑さは？

Well, the one pass is just going to be big O of N, but we know that sorting does take extra memory, or not extra memory, it does take extra time complexity, and that time complexity is N log N.

しかし、ソートには余分なメモリーが必要で、余分なメモリーではなく、余分な時間複雑性が必要で、その時間複雑性はN log Nである。

So that's the bottleneck in this solution.

それがこのソリューションのボトルネックなんだ。

But again, we don't need extra space if you don't count the space that's used by the sorting algorithm.

しかし繰り返しになるが、ソートアルゴリズムが使用するスペースを除けば、余分なスペースは必要ない。

So in this case, we do have a slightly better solution than brute force.

だからこの場合、ブルートフォースより少しマシな解決策がある。

But actually, if we use a little bit extra memory, and it's really a trade-off, if we sacrifice space complexity, we can actually achieve better memory complexity, and let me show you how.

しかし実際には、メモリを少し余分に使えば、これはトレードオフの関係にあり、空間の複雑さを犠牲にすれば、メモリの複雑さを改善することができる。

So suppose we don't sort our input, we're given the default input, but we use extra memory.

つまり、入力をソートせず、デフォルトの入力を与えたとすると、余分なメモリーを使うことになる。

We use a hash set.

ハッシュセットを使う。

But what exactly is a hash set going to do for us?

しかし、ハッシュセットで一体何ができるのだろうか？

It's going to allow us to insert elements into the hash set in big O of one time.

これによって、ハッシュセットに要素を一度に大量に挿入できるようになる。

But it's also going to allow us to check.

でも、これでチェックもできる。

We can ask our hash map, does a certain value exist?

ハッシュ・マップに、ある値が存在するか？

We want to know, does this one exist in the hash map?

このハッシュマップは存在するのか？

Well, if we start at the beginning of the array, so far, nothing is in our hash map.

さて、配列の先頭から始めると、今のところハッシュ・マップには何もない。

So a one does not exist in our hash map.

つまり、このハッシュマップには1は存在しない。

That means this one is not a duplicate.

つまり、これは重複ではないということだ。

You can see that this is an improvement over the brute force.

これが総当たりよりも改善されていることがわかるだろう。

Previously, to determine if this was a duplicate, we had to check every other value in the array.

以前は、重複しているかどうかを判断するために、配列内の他のすべての値をチェックする必要があった。

This time, we don't.

今回は違う。

But after we have checked if this is a duplicate, we do have to add it to our hash set.

しかし、重複かどうかをチェックした後、ハッシュセットに追加しなければならない。

Because later on, if we encounter a one, like over here, then we determine that this is a duplicate because we know that there's already a one in our hash set.

というのも、後で、ここにあるような "1 "に遭遇した場合、ハッシュセットにすでに "1 "があることがわかっているので、これは重複していると判断するからだ。

So next we're going to check two, two is not a duplicate.

次に2をチェックする。2は重複していない。

Add it here.

ここに追加する

Is three a duplicate?

3つは重複するのか？

Nope.

いや。

Add it here.

ここに追加する

One.

一人だ。

Is this a duplicate?

これは重複ですか？

Yep.

そうだね。

There's a one over here.

こっちにもあるよ。

So we return true.

だから我々は真を返す。

This does contain duplicates.

これは重複を含んでいる。

And by the way, since each operation was just big O of one, we had to do that for every value in the input array.

ちなみに、各オペレーションは1つの大きなOであるため、入力配列のすべての値に対してこれを行わなければならなかった。

And we only had to scan through the list of inputs once.

しかも、入力リストに目を通すのは一度だけだった。

The time complexity is going to be big O of n.

時間の複雑さはnの大きなOになる。

But the space complexity, we did have to sacrifice a little bit.

しかし、スペースの複雑さは、少し犠牲にしなければならなかった。

We have to create a hash set.

ハッシュセットを作らなければならない。

And the memory that that hash set will use could be up to the size of the input array, which is n.

そして、そのハッシュセットが使用するメモリは、入力配列のサイズ（n）までとなる。

So we do end up using extra memory.

だから、余計なメモリーを使うことになる。

But that's not too bad.

でも、それも悪くない。

This is about as efficient as we can get in terms of time complexity.

これは、時間の複雑さという点では、私たちが手に入れられるのと同じくらい効率的である。

So let's get into the code now.

それではコードに入ろう。

Okay, so now let's get into the code.

さて、それではコードに入ろう。

So the first thing I'm going to do is create that hash set.

そこで、まず最初にハッシュ・セットを作成する。

In Python, you can do that just like this.

Pythonではこのようにできる。

It's just called a set.

セットと呼ばれるだけだ。

And then the simple thing is just going through every value in the input array nums.

そして単純なのは、入力配列numsのすべての値を調べることだ。

And before we end up adding it to our hash set, because remember, we want to add every one of these values to our hash set just like this.

ハッシュ・セットに追加する前に、覚えておいてほしいのは、このようにハッシュ・セットにこれらの値をすべて追加することだ。

But before we even do that, we want to know, is n a duplicate?

しかし、その前に、nは重複しているのか？

Does this value already exist in our hash set?

この値はハッシュセットに既に存在するか？

And if it does, we know that our array contains duplicates.

もしそうなら、配列に重複があることがわかる。

So we don't even have to continue through the rest of the array.

だから、配列の残りの部分を続ける必要もない。

We can immediately return true because we found a duplicate.

重複が見つかったので、すぐにtrueを返すことができる。

But if it doesn't contain a duplicate, we're going to add that value, then iterate through the rest of the array of nums, and then the loop will exit.

しかし、重複が含まれていなければ、その値を追加し、残りの数値の配列を繰り返し、ループを抜ける。

And then we can return false to indicate that we did not find any duplicates in the array.

そして、配列に重複が見つからなかったことを示すためにfalseを返すことができる。

Now let's run the code to make sure that it works.

では、コードを実行して動作を確認してみよう。

And on the left, you can see that, yes, it does work, and it is about as efficient as we can get.

そして左側には、確かに機能していることがわかる。

So I really hope that this was helpful.

だから、これが役に立ったことを心から願っている。

If it was, please like and subscribe.

もしそうなら、「いいね！」と購読をお願いします。

It supports the channel a lot.

チャンネルを大いにサポートしてくれる。

Consider checking out my Patreon where you can further support the channel.

私のPatreonをチェックし、チャンネルをさらにサポートしてください。

And hopefully I'll see you pretty soon.

またすぐに会えるといいね。

Thanks for watching.

ご視聴ありがとう。