[LeetCode] 3Sum

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution 1: Acceptable O(n*n)

public class Solution {

  public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    HashMap<String,String> map = new HashMap<String,String>();

    Arrays.sort(num);

    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    for(int i=0; i< num.length-1;i++){

      ArrayList<ArrayList<Integer>> slist = twosum(num, i+1,num.length-1, 0-num[i] );
      for(ArrayList<Integer> m:slist){
        m.add(0,num[i]);

        String key= num[i]+"_"+m.get(1)+"_"+m.get(2);
        if(map.get(key) == null){
          list.add(m);
          map.put(key, key);

        }
      }

    }      
    return list;  
  }
     
  public ArrayList<ArrayList<Integer>> twosum(int num[], int start, int end, int sum){
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

    while(start<end){

      if(num[start]+num[end] == sum){

        ArrayList<Integer> sublist = new ArrayList<Integer>();

        sublist.add(num[start]);

        sublist.add(num[end]);

        start++;
        end--;
        list.add(sublist);
      }else if(num[start]+num[end] > sum){

        end--;
      }else{
        start++;
      }
    }

    return list; 

  }

}

Solution 2: O(n*logn)

public class Solution {

 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
  HashMap<String, String> map = new HashMap<String, String>();
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
  for (int i = 0; i <= num.length - 3; i++) {
   ArrayList<ArrayList<Integer>> slist = twosum(num, i + 1,
     num.length - 1, 0 - num[i]);
   for (ArrayList<Integer> m : slist) {
    m.add(0, num[i]);
    String key = num[i] + "_" + m.get(1) + "_" + m.get(2);
    if (map.get(key) == null) {
     list.add(m);
     map.put(key, key);
    }
   }
  }
  return list;
 }

 public ArrayList<ArrayList<Integer>> twosum(int num[], int start, int end,
   int sum) {
  ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
  while (start < end) {
   if (num[start] + num[end] == sum) {
    ArrayList<Integer> sublist = new ArrayList<Integer>();
    sublist.add(num[start]);
    sublist.add(num[end]);
    start++;
    end--;
    list.add(sublist);
   } else if (num[start] + num[end] > sum) {
    end = getMinIndex(num, start + 1, end - 1, sum - num[start]);
   } else {
    start = getMaxIndex(num, start + 1, end - 1, sum - num[end]);
   }
   if (start == -1 || end == -1)
    break;
  }
  return list;
 }

 public int getMinIndex(int[] A, int start, int end, int value) {
  if (start > end) {
   if (A[end] <= value)
    return end;
   return -1;
  }
  if (start == end) {
   if (A[start] <= value)
    return start;
   else
    return start - 1;
  }

  int mid = (start + end) / 2;
  if (value == A[mid]) {
   while (mid < end && A[mid + 1] == value) {
    mid++;
   }
   return mid;
  } else if (value > A[mid]) {
   return getMinIndex(A, mid + 1, end, value);
  } else if (A[mid] > value) {
   return getMinIndex(A, start, mid - 1, value);
  }
  return -1;
 }

 public int getMaxIndex(int[] A, int start, int end, int value) {
  if (start > end) {
   if (A[start] >= value)
    return start;
   return -1;
  }
  if (start == end) {
   if (A[start] >= value)
    return start;
   else
    return start + 1;
  }

  int mid = (start + end) / 2;
  if (value == A[mid]) {
   while (mid > start && A[mid - 1] == value) {
    mid--;
   }
   return mid;
  } else if (value > A[mid]) {
   return getMaxIndex(A, mid + 1, end, value);
  } else if (A[mid] > value) {
   return getMaxIndex(A, start, mid - 1, value);
  }
  return -1;
 }

}

Key Concept: We can use binary search to get closest index