对这个 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，而不是一个哈希表。其次，s.add(arr[i])向 中添加元素HashSet，因此s.contains(temp)可能返回true。例如，假设您正在寻找总和为 8 的一对。如果数组的第一个元素是，则在 中1找不到，而是添加到.8-1Set1Set然后，如果数组的第二个元素是7，您会8-7在 中找到Set（因为您在上一次迭代中添加1了）。Set