Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.

If numbers in the array are not some sort of multi-precision numbers and are, for example, 32-bit integers, you can sort them in 2*32 passes using practically no additional space (1 bit per pass). Or 2*8 passes and 16 integer counters (4 bits per pass).

Details for the 2 iterators solution:

First iterator initially points to first element of the sorted array and advances forward. Second iterator initially points to last element of the array and advances backward.

If sum of elements, referenced by iterators, is less than the required value, advance first iterator. If it is greater than the required value, advance second iterator. If it is equal to the required value, success.

Only one pass is needed, so time complexity is O(n). Space complexity is O(1). If radix sort is used, complexities of the whole algorithm are the same.

If you are interested in related problems (with sum of more than 2 numbers), see "Sum-subset with a fixed subset size" and "Finding three elements in an array whose sum is closest to an given number".

This is a classic interview question from Microsoft research Asia.
How to Find 2 numbers in an unsorted array equal to a given sum.

[1]brute force solution
This algorithm is very simple. The time complexity is O(N^2)

[2]Using binary search
Using bianry searching to find the Sum-arr[i] with every arr[i], The time complexity can be reduced to O(N*logN)

[3]Using Hash
Base on [2] algorithm and use hash, the time complexity can be reduced to O(N), but this solution will add the O(N) space of hash.

[4]Optimal algorithm:

Pseduo-code:

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

or

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. 

And, Is this quesiton completely solved? No. If the number is N. This problem will become very complex.

The quesiton then:
How can I find all the combination cases with a given number?

This is a classic NP-Complete problem which is called subset-sum.
To understand NP/NPC/NP-Hard you'd better to read some professional books.

References:
[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

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. 

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

Create a dictionary with pairs Key (number from the list) and the Value is the number which is necessary to obtain a desired value. Next, check the presence of the pairs of numbers in the list.

def check_sum_in_list(p_list, p_check_sum): l_dict = {i: (p_check_sum - i) for i in p_list} for key, value in l_dict.items(): if key in p_list and value in p_list: return True return False if __name__ == '__main__': l1 = [1, 3, 7, 12, 72, 2, 8] l2 = [1, 2, 2, 4, 7, 4, 13, 32] print(check_sum_in_list(l1, 10)) print(check_sum_in_list(l2, 99)) Output: True Flase 

version 2

import random def check_sum_in_list(p_list, p_searched_sum): print(list(p_list)) l_dict = {i: p_searched_sum - i for i in set(p_list)} for key, value in l_dict.items(): if key in p_list and value in p_list: if p_list.index(key) != p_list.index(value): print(key, value) return True return False if __name__ == '__main__': l1 = [] for i in range(1, 2000000): l1.append(random.randrange(1, 1000)) j = 0 i = 9 while i < len(l1): if check_sum_in_list(l1[j:i], 100): print('Found') break else: print('Continue searching') j = i i = i + 10 Output: ... [154, 596, 758, 924, 797, 379, 731, 278, 992, 167] Continue searching [808, 730, 216, 15, 261, 149, 65, 386, 670, 770] Continue searching [961, 632, 39, 888, 61, 18, 166, 167, 474, 108] 39 61 Finded [Finished in 3.9s] 

If you assume that the value M to which the pairs are suppose to sum is constant and that the entries in the array are positive, then you can do this in one pass (O(n) time) using M/2 pointers (O(1) space) as follows. The pointers are labeled P1,P2,...,Pk where k=floor(M/2). Then do something like this

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

You can handle repeated entries (e.g. two 6's) by storing the indices as digits in base N, for example. For M/2, you can add the conditional

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

But now you have the problem of putting the pairs together.

Does the obvious solution not work (iterating over every consecutive pair) or are the two numbers in any order?

In that case, you could sort the list of numbers and use random sampling to partition the sorted list until you have a sublist that is small enough to be iterated over.

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

`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) *******/ } 

Below code takes the array and the number N as the target sum. First the array is sorted, then a new array containing the remaining elements are taken and then scanned not by binary search but simple scanning of the remainder and the array simultaneously.

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

Shouldn't iterating from both ends just solve the problem?

Sort the array. And start comparing from both ends.

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; 

Time Complexity O(nlogn)

if its a sorted array and we need only pair of numbers and not all the pairs we can do it like this:

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 || i=0 , j=5 sum=21 x=11
1 2 3 9 11 20 || i=0 , j=4 sum=13 x=11
1 2 3 9 11 20 || i=0 , j=4 sum=11 x=11
END

The following code returns true if two integers in an array match a compared integer.

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

Python 2.7 Implementation:

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

Output:

1 + 4 2 + 3 

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) 

I've successfully implemented one solution with Python under O(n+m) time and space cost. The "m" means the target value which those two numbers' sum need equal to. I believe this is the lowest cost could get. Erict2k used itertools.combinations, it'll also cost similar or higher time&space cost comparing my algorithm.

If numbers aren't very big, you can use fast fourier transform to multiply two polynomials and then in O(1) check if coefficient before x^(needed sum) sum is more than zero. O(n log n) total!

// Java implementation using Hashing import java.io.*;

class PairSum { private static final int MAX = 100000; // Max size of 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); } 

}

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