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[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.


Posted

in

,

by

Tags: