哈希表的最差復雜度是n2

Prerequisite:

先決條件：

• Hashing data structure

  散列數據結構

Problem statement:

問題陳述：

Given an array and a sum X, fins any pair which sums to X. Expected time complexity O(n).

給定一個數組和一個和X ，對求和為X的任何一對進行求和。 預期時間復雜度O(n) 。

Example:

例：

Input array:
[4, -1, 6, 5, -2, 2]
Sum, X=2
Output:
Pair {4,-2}
Explanation:
4+(-2)=2 and thus the pair is {4,-2}

Solution:

解：

Obviously, in brute force, we can solve it by checking each pair sums to X or not. In the worst case, it will take O(n²) which is too costly for the problem. Still, the algorithm would be like the following:

顯然，在蠻力中，我們可以通過檢查每對和是否等于X來解決。 在最壞的情況下，將花費O(n ² ) ，這對于該問題而言過于昂貴。 盡管如此，該算法仍將如下所示：

For i=0:n-1
For j=i+1: n-1
If arr[i]+arr[j]==X
Return pair {arr[i],arr[j]}

To solve this efficiently, we will use hashing. What we need to create is a hash table which will be used as our lookup table. The idea is to lookup whether X-current_element exists in the hash table or not. If we find any element in the hash table, then obviously
{X-current_element, current_element} is our desired pair.

為了有效解決此問題，我們將使用哈希。 我們需要創建一個哈希表，該哈希表將用作我們的查找表。 這個想法是要查找哈希表中是否存在X-current_element 。 如果我們在哈希表中找到任何元素，那么顯然
{X-current_element，current_element}是我們想要的對。

Now, we can create a lookup table by simply inserting each element. Then in another loop, we can start finding whether X-current_element is in the hash table or not. Following is the two-pass algorithm,

現在，我們只需插入每個元素即可創建查找表。 然后在另一個循環中，我們可以開始查找X-current_element是否在哈希表中。 以下是兩次通過算法，

Create a hash table using set

使用set創建哈希表

unordered_set<int> myset;
//first pass->building the hash table
For i=0 to n-1
current_element=arr[i]
Add current_element to look up table, myset if it’s not there 
End for

Find the pair

找到一對

//second pass-> finding the pair using the hash table built
For i=0 to n-1
current_element=arr[i]
if(X-current_element is in myset)
the desired pair is { current_element , X-current_element } 
and return 
End for

The time complexity of the algorithm is of course O(n) and space complexity is also O(n) for the hash table.

該算法的時間復雜度當然是O(n)，而哈希表的空間復雜度也是O(n)。

Now, we can further optimize the above algorithm into a single pass.

現在，我們可以將上述算法進一步優化為一次通過。

Instead of creating the hash table in a separate pass, we can do both searching and creating in one pass. The idea is if X-current_element is in the hash table then we are done, otherwise, add this current_element to the hash table.

除了在單獨的過程中創建哈希表，我們還可以一次完成搜索和創建過程。 這個想法是，如果X-current_element在哈希表中，那么我們完成了，否則，請將此current_element添加到哈希表中。

So the algorithm would be:

因此，算法為：

//both searching and looking at a time
For i=0 to n-1
current_element=arr[i]
if(X-current_element is in myset)
the desired pair is { current_element , X-current_element } 
and return 
Else
Add current_element to myset
End for

So, how it guarantees to work?

那么，它如何保證工作呢？

We can show that by our example. Where input array is [4, -1, 6, 5, -2, 2]
If we have used the two-pass algorithm then, we have got {4,-2} as a pair where 4 would be the current_element and-2 would be the X-current_element.

我們可以通過示例來證明這一點。 輸入數組為[4，-1，6，5，-2，2]
如果我們使用了兩次遍歷算法，那么我們將{4，-2}作為一對，其中4是current_element ，-2是X-current_element 。

But if we use the one-pass algorithm we would get the pair as {-2, 4} where -2 would be the current_element and 4 would be X-current_element.

但是，如果使用單次通過算法，則該對將為{-2，4}，其中-2為current_element，而4為X-current_element 。

The reason is when we have 4 as our current_element in our one-pass algorithm then the hash table is empty. Thus we simply add 4.

原因是當我們在一次通過算法中將4作為current_element時 ，哈希表為空。 因此，我們只需添加4。

But when we process -2 as our current_element we have X-(-2) to look for which is 2-(-2) and 4 now exists. So the thing is the one pass is guaranteed to work. Only it will return the pair in reverse order.

但是，當我們將-2作為current_element處理時，我們有X-(-2)來尋找哪個是2-(-2)且現在存在4。 因此，事情是一站式保證有效。 只有它會以相反的順序返回該對。

The time & space complexity of the one-pass algorithm is of course same as the two-pass algorithm since it's big O notation.

一遍算法的時間和空間復雜度當然與二遍算法相同，因為它的O表示法很大。

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
pair<int, int> find_pair_sum(vector<int> arr, int n, int X)
{
unordered_set<int> myset;
for (int i = 0; i < n; i++) {
//pair exists current_element, X-current_element
if (myset.find(X - arr[i]) != myset.end()) {
return make_pair(arr[i], X - arr[i]);
}
//if arr[i] already not there
else if (myset.find(arr[i]) == myset.end()) 
myset.insert(arr[i]);
}
return make_pair(INT_MAX, INT_MAX);
}
int main()
{
cout << "Enter number of input elements,n\n";
int n;
cin >> n;
cout << "Enter the input elements\n";
vector<int> arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
cout << "Enter sum, X\n";
int X;
cin >> X;
pair<int, int> p = find_pair_sum(arr, n, X);
if (p.first == INT_MAX && p.second == INT_MAX)
cout << "No pairs found\n";
else
cout << "The pairs are : " << p.first << ", " << p.second << endl;
return 0;
}

Output:

輸出：

Enter number of input elements,n
6
Enter the input elements
4 -1 6 5 2 -2
Enter sum, X
2
The pairs are : -2, 4

翻譯自: https://www.includehelp.com/data-structure-tutorial/given-an-array-a-and-number-x-check-for-pair-in-a-with-sum-x-set-1.aspx

哈希表的最差復雜度是n2