CareerCup

At best we we do it in O(n^2).

No we cannot.

Follow this link for more details: en.wikipedia.org/wiki/3SUM

I don't think there's a proof that it's impossible, but no subquadratic algorithm is known for general inputs.

Can we take advantage of the fact that atleast one number must be negative.
say a + b + c = 0 and a = - (b+c);
say a is negative here. Then we search for combination of b and c such that summation is equal to negative of a. However our search is limited only for number of -ve number in the list. If list does not contain any negative number we probably can exit at start.

I am thinking we first sort the list
Then for each negative number do a search in nlog(n) time for the two number
O(n log n) + O(number of negative numbers * nlog(n))
= O(number of negative numbers * nlog(n))
For less number of negative numbers, this should work even better as O(nlogn), for large number of negative it should be O(n2)

Any comment

This is probably lame
1) Sort using merge sort O(nlogn)
2) Do 3SUM

#include<stdio.h>

void main()
{
int i,j;

int arr[]={-9,5,3,7,8,17,1};

  for(i=0;i<7;i++)
  {


   int a=arr[i];
     int b=i+1;
     while(b<7)
     {
         int p=arr[b];

         int s=p+a;

         for( j=(b+1);j<=6;j++)
         {
            int y=arr[j];
             int rs=y+s;
         if(rs==0)
         printf("found\n");
         }
 b++;

  }
  }
}

Hey, I have my code here, the solution is O(NlgN), any comments will be appreciated!


import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public static void main(String args[]){
int [] num = {-1, 0, 1, 2, -1, -4};
threeSum(num);
}
public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if(num.length<3 || num.length == 0 || num ==null)
return null;
Arrays.sort(num);
int i=0, j=num.length-1;
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> result;
while(i<j-1){
int v = 0 - num[i] - num[j];
if(binarySearch(num, i+1, j-1, v)){ //do binary search in between
result = new ArrayList<Integer>();
result.add(new Integer(num[i]));
result.add(new Integer(v));
result.add(new Integer(num[j]));
results.add(result);
if(num[i] == num[i+1]&&num[j-1]!=num[j]){ // handle the case when duplicates happens on the left
i++;
}
else if(num[i]!= num[i+1]&&num[j-1]==num[j]){// handle the case when duplicates happens on the right
j--;
}
else{ // if duplicates happens on both or neither happens
i++; j--;
}
}
else if(v > 0) // move to larger ones
i++;
else // move to slower ones
j--;
}
return results;
}
public static boolean binarySearch(int[] a, int lo, int hi, int key){
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return true;
}
return false;
}

}

public static void main(String arg[]){
		int arr[]={-25, -1, -7, -3, 2, 4, 10, 10};
		
		int length = arr.length;
		
		for(int i=0; i<length; i++){
			int a = arr[i];
			int bInd = i + 1;
			int cInd = length-1;
			
			while( bInd<length ){
				int b = arr[bInd];
				int c = arr[cInd];
				if( a+b+c ==0 ){
					System.out.println( ""+a+"/"+b+"/"+c );
					System.exit(0);
				}
				else if( a+b+c>0 ){
					cInd--;
				}
				else{
					bInd++;
				}
			}
		}
		System.out.println("not found");
	}