Найти 2 числа в несортированном массиве, равном заданной сумме

Question

Нам нужно найти пару чисел в массиве, сумма которого равна заданному значению.

A = {6,4,5,7,9,1,2}

Сумма = 10 Тогда пары - {6,4}, {9,1}

У меня есть два решения для этого.

• решение O (nlogn) - сортировка + контрольная сумма с 2 итераторами (начало и конец).
• решение O (n) - хэширование массива. Затем проверяется, существует ли sum-hash[i] в хеш-таблице или нет.

Но проблема в том, что хотя второе решение - это O (n) время, но также используется пространство O (n).

Итак, мне было интересно, можем ли мы сделать это в O (n) времени и O (1) пространстве. И это НЕ домашнее задание!

Answer 1

Используйте сортировку по радиусу на месте и первое решение OP с двумя итераторами, идущими навстречу друг другу.

Если числа в массиве не являются чем-то вроде чисел с множественной точностью и, например, 32-битовые целые числа, вы можете отсортировать их за 2 * 32 прохода, практически не используя дополнительный пробел (1 бит за проход).Или 2 * 8 проходов и 16 целочисленных счетчиков (4 бита за проход).

---

Подробности для решения с двумя итераторами:

Первый итератор изначально указывает на первыйэлемент отсортированного массива и продвигается вперед.Второй итератор изначально указывает на последний элемент массива и продвигается назад.

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

Требуется только один проход, поэтому сложность по времени составляет O (n).Пространственная сложность O (1).Если используется радикальная сортировка, сложности всего алгоритма одинаковы.

---

Если вас интересуют связанные проблемы (с суммой более 2 чисел), см. "Sum-subset withфиксированный размер подмножества " и " Поиск трех элементов в массиве, сумма которых ближе всего к заданному числу ".

Answer 2

Это классический вопрос интервью Microsoft Research Asia.
Как найти 2 числа в несортированном массиве, равном заданной сумме.

[1] решение для перебора
Этот алгоритм очень прост. Сложность времени O (N ^ 2)

[2] Использование бинарного поиска
Используя поиск bianry для поиска Sum-arr [i] с каждым arr [i], временная сложность может быть уменьшена до O (N * logN) * ​​1010 *

[3] Использование хэша
Основываясь на алгоритме [2] и использовании хэша, временная сложность может быть уменьшена до O (N), но это решение добавит пространство хэша O (N).

[4] Оптимальный алгоритм:

1019 * * Pseduo-код:

for(i=0;j=n-1;i<j)
   if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);

или

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.

И, этот вопрос полностью решен? Нет. Если число равно N. Эта проблема станет очень сложной.

Задание тогда:
Как я могу найти все комбинации случаев с данным номером?

Это классическая задача NP-Complete, которая называется subset-sum.
Чтобы понять NP / NPC / NP-Hard, вам лучше прочитать несколько профессиональных книг.

Ссылки:
[1] http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2] http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 3

for (int i=0; i < array.size(); i++){
  int value = array[i];
  int diff = sum - value; 
  if (! hashSet.contains(diffvalue)){
      hashSet.put(value,value);
  } else{
       printf(sum = diffvalue + hashSet.get(diffvalue));
  } 
}

--------
Sum being sum of 2 numbers.

Answer 4

    public void printPairsOfNumbers(int[] a, int sum){
    //O(n2)
    for (int i = 0; i < a.length; i++) {
        for (int j = i+1; j < a.length; j++) {
            if(sum - a[i] == a[j]){
                //match..
                System.out.println(a[i]+","+a[j]);
            }
        }
    }

    //O(n) time and O(n) space
    Set<Integer> cache = new HashSet<Integer>();
    cache.add(a[0]);
    for (int i = 1; i < a.length; i++) {
        if(cache.contains(sum - a[i])){
            //match//
            System.out.println(a[i]+","+(sum-a[i]));
        }else{
            cache.add(a[i]);
        }
    }

}

Answer 5

Если вы предполагаете, что значение M, для которого пары должны суммироваться, является постоянным и что записи в массиве положительны, то вы можете сделать это за один проход (O(n) время), используя M/2 указатели (O(1) пробел) следующим образом. Указатели помечены P1,P2,...,Pk, где k=floor(M/2). Затем сделайте что-то вроде этого

for (int i=0; i<N; ++i) {
  int j = array[i];
  if (j < M/2) {
    if (Pj == 0)
      Pj = -(i+1);   // found smaller unpaired
    else if (Pj > 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  } else
    if (Pj == 0)
      Pj = (i+1);    // found larger unpaired
    else if (Pj < 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  }
}

Вы можете обрабатывать повторяющиеся записи (например, два 6), сохраняя индексы, например, в виде цифр в базе N. Для M/2 вы можете добавить условное

  if (j == M/2) {
    if (Pj == 0)
      Pj = i+1;      // found unpaired middle
    else
      print(Pj-1,i); // found a pair
      Pj = 0;
  } 

Но теперь у вас проблема собрать пары.

Answer 6

    public static void Main(string[] args)
    {
        int[] myArray =  {1,2,3,4,5,6,1,4,2,2,7 };
        int Sum = 9;

            for (int j = 1; j < myArray.Length; j++)
            {                    
                if (myArray[j-1]+myArray[j]==Sum)
                {
                    Console.WriteLine("{0}, {1}",myArray[j-1],myArray[j]);
                }
            }            
        Console.ReadLine();
    }

Answer 7

Если числа не очень большие, вы можете использовать быстрое преобразование Фурье для умножения двух полиномов, а затем в O (1) проверить, равен ли коэффициент перед суммой x ^ (необходимая сумма) больше нуля. O (n log n) всего!

Answer 8

https://github.com/clockzhong/findSumPairNumber

#! /usr/bin/env python
import sys
import os
import re


#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces)...\n")
numberList=[int(i) for i in numberListStr.split()]
print 'you have input the following number list:'
print numberList

#get the sum target value
sumTargetStr=raw_input("Please input your target number:\n")
sumTarget=int(sumTargetStr)
print 'your target is: '
print sumTarget


def generatePairsWith2IndexLists(list1, list2):
    result=[]
    for item1 in list1:
        for item2 in list2:
            #result.append([item1, item2])
            result.append([item1+1, item2+1])
    #print result
    return result

def generatePairsWithOneIndexLists(list1):
    result=[]
    index = 0
    while index< (len(list1)-1):
        index2=index+1
        while index2 < len(list1):
            #result.append([list1[index],list1[index2]])
            result.append([list1[index]+1,list1[index2]+1])
            index2+=1
        index+=1
    return result


def getPairs(numList, target):
    pairList=[]
    candidateSlots=[] ##we have (target-1) slots 

    #init the candidateSlots list
    index=0
    while index < target+1:
        candidateSlots.append(None)
        index+=1

    #generate the candidateSlots, contribute O(n) complexity
    index=0
    while index<len(numList):
        if numList[index]<=target and numList[index]>=0:
            #print 'index:',index
            #print 'numList[index]:',numList[index]     
            #print 'len(candidateSlots):',len(candidateSlots)
            if candidateSlots[numList[index]]==None:
                candidateSlots[numList[index]]=[index]
            else:
                candidateSlots[numList[index]].append(index)
        index+=1

    #print candidateSlots

    #generate the pairs list based on the candidateSlots[] we just created
    #contribute O(target) complexity
    index=0
    while index<=(target/2):
        if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
            if index!=(target-index):
                newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
            else:
                newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
            pairList+=newPairList
        index+=1

    return pairList

print getPairs(numberList, sumTarget)

Я успешно внедрил одно решение с Python за O (n + m) затрат времени и пространства.«M» означает целевое значение, которому должна равняться сумма этих двух чисел.Я считаю, что это самая низкая цена, которую можно получить.Erict2k использовал itertools.combinsk, он также будет стоить аналогичные или более высокие затраты времени и пространства по сравнению с моим алгоритмом.

Answer 9

Python 2.7 Реализация:

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
    print str(n[0]) + " + " + str(n[1])

Вывод:

1 + 4
2 + 3

Answer 10

Следующий код возвращает true, если два целых числа в массиве соответствуют сравниваемому целому числу.

 function compareArraySums(array, compare){

        var candidates = [];

        function compareAdditions(element, index, array){
            if(element <= y){
                candidates.push(element);
            }
        }

        array.forEach(compareAdditions);

        for(var i = 0; i < candidates.length; i++){
            for(var j = 0; j < candidates.length; j++){
                if (i + j === y){
                    return true;
                }
            }
        }
    }