Смущенный с этим вопросом интервью алгоритма HashMap - PullRequest
Новая
       3

Смущенный с этим вопросом интервью алгоритма HashMap

0 голосов
/ 20 января 2019

Я изучаю вопросы интервью и столкнулся с этим вопросом, который действительно смущает меня.Я знаю, как сделать базовое решение 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), когда в хеш-таблицу ничего не помещается.Так как он может содержать сумму - я?

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

1 Ответ

0 голосов
/ 20 января 2019

Прежде всего, это HashSet, а не хеш-таблица.

Во-вторых, s.add(arr[i]) добавляет элементы в HashSet, поэтому s.contains(temp) может вернуть true.

Например, предположим, что вы ищете пару с суммой 8.

  • Если первый элемент массива равен 1, вы не найдете 8-1в Set, но вы добавляете 1 к Set.
  • Затем, если второй элемент массива равен 7, вы найдете 8-7 в Set (так каквы добавили 1 к Set в предыдущей итерации).
...