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[0] - 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; this.addTriple(ai,bi,ci); 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.