Hello world! I am sharing this very fast, heap based algorithm. I will explain the notion behind my alg. first. Then, I will show some benchmark result between my algorithm and hash based algorithms with length ranging from 2^5 to 2^23.

First things first, the idea:

- We know that if a+b=target, then a<target/2 and b>target/2, or a,b=target/2

Therefore, if we first partition our sequence into 3 parts (A<target/2;B=target/2;C>target/2), we can simplify our search. If part B contains two numbers, they are the answers. Otherwise, we will need to proceed to check part A and C. (complexity O(n)) - Let the largest number of part A plus the smallest number of part C. If the sum is target, lucky! You get the result. Otherwise, the sum can be either smaller than the target or bigger than the target. If the sum is smaller, for example, the smallest number from C can be discarded, because other numbers from A, that is smaller than the largest number from A, will only produce a even smaller sum, when added to our smallest number from C. Since each comparison eliminates a number from A or C, we have O(n) for comparison.
- Notice that we do not need to have the numbers sorted. if we make use of max and min heap for A and C respectively, we can try to find our two numbers while sorting our sequence. We need O(n) for building heaps, and O(nlogn) to have our sequence partially sorted.

Quite to my surprise, this alg. runs at most twice as fast as hash based alg. (see below)

The code is below for inspection. Have fun.

About hash based O(n) solution: (see topic 3294 for code)

I did the benchmark because several other posts have pointed out that the hash based algorithm is slow, and there are also arguments that hash based alg. is not O(n). To settle the debates, I ran a few benchmarks on my local machine. The test sequences were generated randomly, put into a unordered_set and checked to eliminate adding numbers that sum up to target. Then I can control where the answer to put inside the sequence.

Anyway, with these long sequences, I got the following the result (averages of 100 to 3 repeats, unit: us):

```
N hash alg. heap alg.
32 29 12
64 61 25
128 117 56
256 235 121
512 462 261
1024 925 548
2048 1932 1185
4096 3951 2462
8192 8042 5229
16384 16372 11019
32768 33816 23462
65536 80363 49982
131072 176597 105490
262144 367625 224972
524288 755913 490834
1048576 1483167 1089676
2097152 3038274 2418336
4194304 6295344 5311888
8388608 13271319 11692934
```

You may copy the data into spreadsheet and plot them out. Even better, calculate the slopes like in calculus 101, plot the change in slope out too. O(n) solution should have a constant slope.

Heap based alg. is O(nlogn), no doubt. Hash based alg. is more or less O(n) if we ignore a bump in the slope at N=~2^16, where the slope increased from 1 to 1.5 and stabilizes there afterward. Whatever the bump is, hash based alg. is O(n), in theory and mostly in practice, but hashing and conflict resolution are probably so computationally expensive, that hash based alg is slower than heap based alg even for reasonable large datasets. The slope of heap based alg. does increase, but it starts from ~0.4 to ~1.4, the slope never surpass the slope of hash based alg (~1, and then ~1.5) within my test range. Yes, eventually, heap based alg should fall behind, but not on my machine (2^24 ints overflow my 4GB RAM).

```
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target){
vector<int> vecResult(2);
int size=numbers.size();
int* tmpArr=new int[size];
int left=0,right=size-1,swapSpace;
int endL,startR,endR=size-1;
//copy numbers vector into tmpArr
for (int i=0;i<size;i++){
tmpArr[i]=numbers[i];
}
//partitions tmpArr into A'<=half and C>half
while (left<=right){
if (tmpArr[left]*2<=target){
left++;
}
else if (tmpArr[right]*2>target){
right--;
}
else {
swapSpace=tmpArr[left];
tmpArr[left]=tmpArr[right];
tmpArr[right]=swapSpace;
left++;
right--;
}
}
startR=left;
//partitions tmpArr part A' from above into A<half and B=half
left=0;
while (left<=right){
if (tmpArr[left]*2<target){
left++;
}
else if (tmpArr[right]*2==target){
right--;
}
else {
swapSpace=tmpArr[left];
tmpArr[left]=tmpArr[right];
tmpArr[right]=swapSpace;
left++;
right--;
}
}
endL=right;
//now, the tmpArr is partitioned into 3 parts:
//A, B, C, where for all x in A, x<half
// for all x in B, x==half
// for all x in C, x>half
if (startR-endL-1==2){
//when two number==half is found
//find such two numbers in the original vec
int pos=0;
for (int i=0;pos<2 && i<size;i++){
if ( numbers[i]*2==target ){
vecResult[pos]=i;
pos++;
}
}
return vecResult;
}
else {
//when two number==half is NOT found
//build max heap on the first part of vector that contains numbers smaller than half
//build min heap on the thrid part of vector that contains numbers largerer than half
make_heap(tmpArr,tmpArr+endL+1); //max heap
make_heap(tmpArr+startR,tmpArr+endR+1,greater<int>()); //min heap
while (endL>=0 && endR-startR>=0){
if (tmpArr[0]+tmpArr[startR]>target){
//the biggest number (say a) in part A plus the smallest number in C is larger than target
//we have: for any x in C, a+x>target
//remove a from A
pop_heap(tmpArr,tmpArr+endL+1);
endL--;
}
else if (tmpArr[0]+tmpArr[startR]<target){
//the biggest number in part A plus the smallest number (say c) in C is smaller than target
//we have: for any x in A, x+c<target
//remove c from C
pop_heap(tmpArr+startR,tmpArr+endR+1,greater<int>());
endR--;
}
else {
//found tmpArr[0]+tmpArr[startR]==target
for (int i=0,pos=0; pos<=1 && i<size;i++){
if ( numbers[i]==tmpArr[0] || numbers[i]==tmpArr[startR]){
vecResult[pos]=i;
pos++;
}
}
break;
}
}
return vecResult;
}
delete [] tmpArr;
}
};
```