被这个HashMap算法面试题搞糊涂了

Question

我正在研究面试问题，遇到了这个让我很困惑的问题。我知道如何做基本的 O(n^2) 解决方案，但是 HashTable O(n) 没有任何意义。

static void printpairs(int arr[],int sum) 
{        
    HashSet<Integer> s = new HashSet<Integer>(); 
    for (int i=0; i<arr.length; ++i) 
    { 
        int temp = sum-arr[i]; 

        // checking for condition 
        if (temp>=0 && s.contains(temp)) 
        { 
            System.out.println("Pair with given sum " + 
                                sum + " is (" + arr[i] + 
                                ", "+temp+")"); 
        } 
        s.add(arr[i]); 
    } 
}

让我困惑的部分是检查条件的部分。当哈希表中没有任何内容时，它会执行 s.contains(temp) 。那么它怎么可能包含 sum - i 呢？

https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

Answer 1

首先，它是一个HashSet，而不是散列table。

其次，s.add(arr[i]) 向 HashSet 添加元素，因此 s.contains(temp) 可能 return true。

例如，假设您要查找和为 8 的一对。

如果数组的第一个元素是1，你在Set中没有找到8-1，但是你在Set中添加了1 =].
然后，如果数组的第二个元素是 7，您会在 Set 中找到 8-7（因为您将 1 添加到 Set 在上一次迭代中）。

被这个HashMap算法面试题搞糊涂了

Confused with this HashMap algorithm interview question

java

algorithm

hashtable

hashmap