проверка, если 2 числа массива складываются в I

Question

Я видел вопрос интервью следующим образом: Дайте несортированный массив целых чисел A и и целое число I, выясните, если любые два члена A складываются в I.

какие-нибудь подсказки?

сложность времени должна быть меньше

Answer 1

Вставьте элементы в хеш-таблицу.

При вставке x проверьте, существует ли I-x.O(n) ожидаемое время.

В противном случае сортируйте массив по возрастанию (от индекса 0 до n-1).Имейте два указателя, один на максимуме и один на минимуме (назовите их M и m соответственно).

If a[M] + a[m] > I then M-- 
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

Answer 2

Если у вас есть диапазон, в котором находятся целые числа, вы можете использовать решение для сортировки по типу подсчета, где вы сканируете массив и подсчитываете массив. Например, у вас есть целые числа

input = [0,1,5,2,6,4,2]

И вы создаете массив следующим образом:

count = int[7]

которые (в Java, C # и т. Д.) Подходят для подсчета целых чисел от 0 до 6.

foreach integer in input
    count[i] = count[i] + 1

Это даст вам массив [1,1,2,0,1,1,1]. Теперь вы можете сканировать этот массив (половину) и проверить, есть ли целые числа, которые складываются до i, как

for j = 0 to count.length - 1
    if count[j] != 0 and count[i - j] != 0 then // Check for array out-of-bounds here
         WUHUU! the integers j and i - j adds up

В целом, этот алгоритм дает вам O(n + k), где n - результат сканирования по вводу длины n, а k - просмотр массива счетчиков длины k (целые числа от 0 до k - 1). Это означает, что если n > k, то у вас есть гарантированное решение O(n).

Answer 3

Например, цикл и добавление возможного числа для установки или хэширования и, если найдено, просто вернуть его.

Answer 4

1. сортировка массива
2. для каждого элемента X в A, выполнить двоичный поиск для I-X.Если I-X находится в A, у нас есть решение.

Это O(nlogn).

Если A содержит целые числа в заданном (достаточно малом) диапазоне, мы можем использовать трюк, чтобы сделать это O(n):

1. у нас есть массив V.Для каждого элемента X в A мы увеличиваем V[X].
2. , когда мы увеличиваем V[X], мы также проверяем, V[I-X] равно >0.Если это так, у нас есть решение.

Answer 5

public static boolean findSum2(int[] a, int sum) {
        if (a.length == 0) {
            return false;
        }
        Arrays.sort(a);


        int i = 0;
        int j = a.length - 1;
        while (i < j) {
            int tmp = a[i] + a[j];
            if (tmp == sum) {
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                return true;
            } else if (tmp > sum) {
                j--;
            } else {
                i++;
            }
        }
        return false;
}

Answer 6

O(n) time and O(1) space

Если массив отсортирован, есть решение с O (n) сложностью по времени.

Предположим, что массив равен array = {0, 1, 3, 5, 8, 10, 14}

И наш x1 + x2 = k = 13, поэтому выводимдолжно быть = 5, 8

1. Взять два указателя, один в начале массива, один в конце массива
2. Добавить оба элемента в ptr1 и ptr2 array[ptr1] + array[ptr2]
3. if sum > k then decrement ptr2 else increment ptr1
4. Повторите шаги 2 и 3 до ptr1! = Ptr2

То же самое подробно объясняется здесь.Похоже на интервью Амазонки Вопрос http://inder -gnu.blogspot.com / 2007/10 / find-two-nos-in-array-who-sum-x.html

Answer 7

Реализация в Python

def func(list,k):
temp={} ## temporary dictionary
for i in range(len(list)):
    if(list[i] in temp): ## if temp already has the key just increment its value
        temp[list[i]] +=1
    else:  ## else initialize the key in temp with count as 0
        temp[list[i]]=0 

    if(k-list[i] in temp and ((k/2 != list[i]) or temp[list[i]]>=1)): ## if the corresponding other value to make the sum k is in the dictionary and its either not k/2 or the count for that number is more than 1
        return True

return False

Входной сигнал: list - список чисел (A в вопросе выше) ...
k сумма (я в вопросе выше) ....

Функция выводит True , если в списке существует пара, сумма которой равна k, и False в противном случае ...

Я использую словарь, ключом которого является элемент в массиве (списке), а значением является счетчик этого элемента (количество раз, которое этот элемент присутствует в этом списке). Среднее время выполнения сложность O (n).

Эта реализация также заботится о двух важных крайних случаях:

• повторяющиеся числа в списке и
• не добавляя один и тот же номер дважды.

Answer 8

Разделить массив на две группы <= I / 2 и> I / 2.Затем разделите их на <= I / 4,> I / 4 и <= 3I / 4,> 3I / 4 и повторите шаги для log (I) и проверьте пары, соединяющиеся снаружи, например 1I / 8 <= и> 7I/ 8 и если они оба содержат хотя бы один элемент, они добавляют к I. Это займет n.Log (I) + n / 2 шагов и для I

Answer 9

Вот решение, которое учитывает дублирующиеся записи.Он написан на javascript и предполагает, что массив отсортирован.Решение выполняется за время O (n) и не использует никакой дополнительной памяти, кроме переменной.Выберите алгоритм сортировки по вашему выбору.(radix O (kn)!) и затем проведите массив через этого ребенка.

var count_pairs = function(_arr,x) {
  if(!x) x = 0;
  var pairs = 0;
  var i = 0;
  var k = _arr.length-1;
  if((k+1)<2) return pairs;
  var halfX = x/2; 
  while(i<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=i) pairs+=(comb++);
        break;
      }
      // count pair and k duplicates
      pairsThisLoop++;
      while(_arr[--k]==curK) pairsThisLoop++;
      // add k side pairs to running total for every i side pair found
      pairs+=pairsThisLoop;
      while(_arr[++i]==curI) pairs+=pairsThisLoop;
    } else {
      // if we are at a mid point
      if(curK==curI) break;
      var distK = Math.abs(halfX-curK);
      var distI = Math.abs(halfX-curI);
      if(distI > distK) while(_arr[++i]==curI);
      else while(_arr[--k]==curK);
    }
  }
  return pairs;
}

Я решил это во время интервью для большой корпорации.Они взяли это, но не я.Так что это для всех.

Начните с обеих сторон массива и медленно продвигайтесь внутрь, проверяя количество дубликатов, если они существуют.

Он только подсчитывает пары, но может быть переработан в

• найти пары
• найти пары
• найти пары> x

Наслаждайтесь и не забывайте поднимать, еслиэто лучшее решение!

Answer 10

здесь решение O (n) в java, использующее дополнительное пространство O (n). Это использует hashSet, чтобы реализовать это

http://www.dsalgo.com/UnsortedTwoSumToK.php