对这个 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