# 3SUM algorithm tweak

http://en.wikipedia.org/wiki/3SUM this is the algorithm. I just thought that I can start from the middle, the rationale is that I have the work done not to be due.

I wrote down the value of an example and try to iterate on the outer cycle starting from middle (max value + min value) then down to the lower value, what happen (hand running iterations) is that I never have to consider the excluded item in the preceeding iteration (outer iteration), thus I added a start point keeper array.

This is almost correct, I doubt nobody else had ever tried it, but it look to me no more than n log n complexity, even if it is had to proof. I just paste the algorithm here, please do not blame me, just point out that this is a know solution.

```public class Sum3SubQ {
private int[] Narray;

private int[] CStart;

public Sum3SubQ(int N) {
Narray = new int[N];
CStart = new int[N];
int Min = -100000;
int Max = 100000;
for(int i = 0; i<N; i++) {
CStart[i] = 0;
Narray[i] = Min + (int)(Math.random() * ((Max - Min) + 1));
}
}

public void FindSum0(){
java.util.Arrays.sort(Narray);
int pivot = - Narray - Narray[Narray.length -1];
int idx = -1;
for(int i=0;i<Narray.length-1;i++) {
if(Narray[i]==pivot) {
idx = i;
break;
}
if(Narray[i]>pivot) {
idx = i;
break;
}
}
if (idx == -1) return; // no solution
for (int ai = idx; ai>=0; ai--) { // N/2 at most
int bi = Narray.length-1; // last
int ci = CStart[bi]; // in this iteration ai is lower, this Narray[ai] is a lower value
// thus start at least from the one checked before.
while (ai<bi && bi>ci) {
if(ci == ai) {
ci++;
}
if(Narray[ai]+Narray[bi]+Narray[ci] == 0) {
//sign Cstart[bi] with ci+1
CStart[bi] = ci+1;
bi--;
} else if(Narray[ai]+Narray[bi]+Narray[ci] < 0) {
CStart[bi] = ci;
ci++;
} else {
bi--;
}
}
}

}

private void addTriple(int a, int b, int c) {
System.out.println("IDX: "+ a +","+ b +","+ c + " Numbers: " + Narray[a] +","+ Narray[b] +","+ Narray[c]);
}

}```

It look correct to me, at least.