Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

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.

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

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

Это классическая NP-полная проблема, называемая подмножеством.
Чтобы понять 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

Ответ 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.

Ответ 4

Если вы предполагаете, что значение 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;
  } 

Но теперь у вас есть проблема с объединением пар.

Ответ 5

    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]);
        }
    }

}

Ответ 6

Не работает ли очевидное решение (итерация по каждой последовательной паре) или два числа в любом порядке?

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

Ответ 7

public static ArrayList<Integer> find(int[] A , int target){
    HashSet<Integer> set = new HashSet<Integer>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    int diffrence = 0;
    for(Integer i : A){
        set.add(i);
    }
    for(int i = 0; i <A.length; i++){
        diffrence = target- A[i];
    if(set.contains(diffrence)&&A[i]!=diffrence){
        list.add(A[i]);
        list.add(diffrence);
        return list;
    }
     }
    return null;
}

Ответ 8

`package algorithmsDesignAnalysis;

 public class USELESStemp {
 public static void main(String[] args){
    int A[] = {6, 8, 7, 5, 3, 11, 10}; 

    int sum = 12;
    int[] B = new int[A.length];
    int Max =A.length; 

    for(int i=0; i<A.length; i++){
        B[i] = sum - A[i];
        if(B[i] > Max)
            Max = B[i];
        if(A[i] > Max)
            Max = A[i];

        System.out.print(" " + B[i] + "");

    } // O(n) here; 

    System.out.println("\n Max = " + Max);

    int[] Array = new int[Max+1];
    for(int i=0; i<B.length; i++){
        Array[B[i]] = B[i];
    } // O(n) here;

    for(int i=0; i<A.length; i++){  
    if (Array[A[i]] >= 0)
        System.out.println("We got one: " + A[i] +" and " + (sum-A[i]));
    } // O(n) here;

} // end main();

/******
Running time: 3*O(n)
*******/
}

Ответ 9

Ниже код берет массив и число N в качестве целевой суммы. Сначала массив сортируется, затем новый массив, содержащий остальные элементы берутся и затем сканируются не бинарным поиском но простое сканирование остатка и массива одновременно.

public static int solution(int[] a, int N) {

    quickSort(a, 0, a.length-1);    // nlog(n)

    int[] remainders = new int[a.length];

    for (int i=0; i<a.length; i++) {
        remainders[a.length-1-i] = N - a[i];     // n
    }

    int previous = 0;

    for (int j=0; j<a.length; j++) {            // ~~ n

        int k = previous;

        while(k < remainders.length && remainders[k] < a[j]) {
            k++;
        }

        if(k < remainders.length && remainders[k] == a[j]) {
            return 1;
        }

        previous = k;
    }

    return 0;
}

Ответ 10

Не следует ли итерация с обоих концов решить проблему?

Сортировка массива. И начните сравнивать с обоих концов.

if((arr[start] + arr[end]) < sum) start++;
if((arr[start] + arr[end]) > sum) end--;
if((arr[start] + arr[end]) = sum) {print arr[start] "," arr[end] ; start++}
if(start > end)  break;

Сложность времени O(nlogn)

Ответ 11

если его массив отсортирован, и нам нужна только пара чисел, а не все пары, мы можем сделать это следующим образом:

public void sums(int a[] , int x){ // A = 1,2,3,9,11,20 x=11
    int i=0 , j=a.length-1;
    while(i < j){
      if(a[i] + a[j] == x) system.out.println("the numbers : "a[x] + " " + a[y]);
      else if(a[i] + a[j] < x) i++;
      else j--;
    }
}

1 2 3 9 11 20 || я = 0, j = 5 sum = 21 x = 11
1 2 3 9 11 20 || я = 0, j = 4 sum = 13 x = 11
1 2 3 9 11 20 || я = 0, j = 4 sum = 11 x = 11
END

Ответ 12

Следующий код возвращает 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;
                }
            }
        }
    }

Ответ 13

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

Ответ 14

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.combinations, он также будет стоить аналогичные или более высокие временные и объемные затраты, сравнивающие мой алгоритм.

Ответ 15

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

Ответ 16

//реализация Java с использованием Hashing import java.io. *;

класс PairSum {   private static final int MAX = 100000;//Максимальный размер Hashmap

static void printpairs(int arr[],int sum)
{
    // Declares and initializes the whole array as false
    boolean[] binmap = new boolean[MAX];

    for (int i=0; i<arr.length; ++i)
    {
        int temp = sum-arr[i];

        // checking for condition
        if (temp>=0 && binmap[temp])
        {
            System.out.println("Pair with given sum " +
                                sum + " is (" + arr[i] +
                                ", "+temp+")");
        }
        binmap[arr[i]] = true;
    }
}

// Main to test the above function
public static void main (String[] args)
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    printpairs(A,  n);
}

}

Ответ 17

    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();
    }