So today let's solve contains duplicate.

所以，今天讓我們來解決其中的重複問題。

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

這是我們一直在研究的盲人 75 問題列表中的另一個問題。

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?

如果數字列表中的任何值至少出現兩次，但也可能出現三次或四次，我們希望返回 true，對嗎？

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

只要至少兩次，我們就希望返回 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.

如果沒有任何值至少出現兩次，基本上就意味著數組中的每個值都是不同的。

So let's take a look at an example.

讓我們來看一個例子。

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

我們有一個、兩個、三個，然後又有一個。

So of course this has duplicates, right?

所以，這當然有重複的地方，對嗎？

So we return true.

是以，我們返回 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.

是以，光是檢查第一個數字是否重複，就需要花費大量的 O of n 時間。

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

然後，我們必須對每個數字都這樣做。

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

然後，我們必須檢查第二個數字是否重複？

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.

第三個和最後一個也是這樣。

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.

第二種可以幫助我們的方法是分類。

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.

如果我們對輸入內容進行排序，那麼數組中的任何重複內容都會存在，我們可以清楚地看到，在數組的開頭有兩個重複內容，它們將相鄰存在。

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.

在此過程中，我們將比較數組中的兩個相鄰數組，檢查它們是否重複。

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.

在本例中，我們發現這兩個相鄰值是重複的，是以可以返回 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 的大 O，但我們知道排序需要額外的內存，或者說不是額外的內存，而是額外的時間複雜度，而時間複雜度是 N 對數 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?

三個是重複的嗎？

Nope.

沒有。

Add it here.

在此添加。

One.

一個

Is this a duplicate?

這是重複的嗎？

Yep.

是的。

There's a one over here.

這裡有一個

So we return true.

是以，我們返回 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.

順便說一下，由於每次操作都是一個大 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.

感謝觀看。