Algorithm to find the pair of numbers in an integer array whoes sum are equal

Algorithm to find the pair of numbers in an integer array whoes sum are equal. ex {1 2 3 4 6}

here{3 2} { 4 1} should be the output, because the sum is 3+2=5, 4+1=5.

Here the main thing is the complexity shld be O(n). Please help me if we find any solutions for开发者_JS百科 this?

---

Are you sure that the problem is solvable at all in O(n)?

Imagine the case when the input sequence is just {0, 0, 0, 0, 0, 0, ..., 0}. Here every two pairs satisfy the condition. Just listing all the pairs is already at least O(n^2).

---

I think it's possible:

you need a second array tmp = {} with the length of sum.

sum = 5
array = {1,2,3,4,6}
for every i in array{
    if i>=sum:
        continue
    if tmp[i] != 0 {
        output {i,(sum-i)}
        tmp[i] = 0
        continue
    }

    tmp[sum-i] := i
}

that's it. so simple and with O(n)

cons:

1. it won't find a pair like {5,0}, therefore you have to use real Integer-Objects to check at line 6 against NULL and assign NULL in line 8,
2. pairs with a negative number won't work.

---

I am not sure whether this is possible to do effectively.

According to the given information, the array is not sorted and you don't know the expected summation you will need to traverse through the array twice.

Think of a search algorithm. the least complex one, the linear (sequential) search has the O(n) complexity. It is just for traverse the array. If you know the sum you are expecting then the case is similar, and actually what you need to do is a linear search. For anything else you get a higher complexity.

But in your case you don't know the sum so you will need to traverse over more than one time. My head says this is O(n log n) or O(n^2).

Perhaps there might be a solution that utilizes more data structures, perhaps a summation table (2D array???) but the chance of existing such a solution is low.

---

The problem, as stated, seems to be missing some constraints that would be helpful. The first I would like to suggest, each integer of the array should be distinct. At the very least, the output should be of unique pairs.

Another constraint that may or may not apply to a specific problem domain is a sorted array. This constraint, when true, suggest a simple algorithm. Start 2 pointers, left and right, the their respective ends. If the sum matches, output it, increment left and decrement right. If not a match, then decrement the right pointer if the sum is too large, or increment the left (too small). Continue to adjust left and right until they cross somewhere in the middle.

For an unsorted array. Create a hash-table, insert all of the integers. Walk through the array again, this time search the hash-table for the value to satisfy the required sum. If the hash function is perfect (something that can be tricky to achieve), then the expected runtime is O(n).