LeetCode - 3Sum

LeetCode – 3Sum

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.

https://discuss.leetcode.com/topic/8125/concise-o-n-2-java-solution

The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {//\\
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;//
                    while (lo < hi && num[hi] == num[hi-1]) hi--;\\
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}

https://discuss.leetcode.com/topic/28857/easiest-java-solution

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i + 2 < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {              // skip same result
            continue;
        }
        int j = i + 1, k = nums.length - 1;  
        int target = -nums[i];
        while (j < k) {
            if (nums[j] + nums[k] == target) {
                res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                j++;
                k--;
                while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
                while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result
            } else if (nums[j] + nums[k] > target) {
                k--;
            } else {
                j++;
            }
        }
    }
    return res;
}

EPI Java Solution: ThreeSum.java 

  public static boolean hasThreeSum(List<Integer> A, int t) {

    Collections.sort(A);

    for (Integer a : A) {

      // Finds if the sum of two numbers in A equals to t - a.

      if (hasTwoSum(A, t - a)) {

        return true;

      }

    }

    return false;

  }

  private static boolean hasTwoSum(List<Integer> A, int t) {

    int j = 0, k = A.size() - 1;

    while (j <= k) {

      if (A.get(j) + A.get(k) == t) {

        return true;

      } else if (A.get(j) + A.get(k) < t) {

        ++j;

      } else { // A[j] + A[k] > t.

        --k;

      }

    }

    return false;

  }
http://www.programcreek.com/2012/12/leetcode-3sum/
O(n^2)

public ArrayList<ArrayList<Integer>> threeSum(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();   if (num.length < 3) return result;   // sort array Arrays.sort(num);   for (int i = 0; i < num.length - 2; i++) { // //avoid duplicate solutions if (i == 0 || num[i] > num[i - 1]) {   int negate = -num[i];   int start = i + 1; int end = num.length - 1;   while (start < end) { //case 1 if (num[start] + num[end] == negate) { ArrayList<Integer> temp = new ArrayList<Integer>(); temp.add(num[i]); temp.add(num[start]); temp.add(num[end]);   result.add(temp); start++; end--; //avoid duplicate solutions while (start < end && num[end] == num[end + 1]) end--;   while (start < end && num[start] == num[start - 1]) start++; //case 2 } else if (num[start] + num[end] < negate) { start++; //case 3 } else { end--; } }   } }   return result; }

http://www.cnblogs.com/springfor/p/3859670.html 

同时，解决duplicate问题，也可以通过挪动指针来解决判断，当找到一个合格结果时，将3个加数指针挪动到与当前值不同的地方，才再进行继续判断

 1     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
 2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 3         if(num.length<3||num == null)
 4             return res;
 5         
 6         Arrays.sort(num);
 7         
 8         for(int i = 0; i <= num.length-3; i++){
 9             if(i==0||num[i]!=num[i-1]){//remove dupicate
10                 int low = i+1;
11                 int high = num.length-1;
12                 while(low<high){
13                     int sum = num[i]+num[low]+num[high];
14                     if(sum == 0){
15                         ArrayList<Integer> unit = new ArrayList<Integer>();
16                         unit.add(num[i]);
17                         unit.add(num[low]);
18                         unit.add(num[high]);
19                         
20                         res.add(unit);
21                         
22                         low++;
23                         high--;
24                         
25                         while(low<high&&num[low]==num[low-1])//remove dupicate
26                             low++;
27                         while(low<high&&num[high]==num[high+1])//remove dupicate
28                             high--;
29                             
30                     }else if(sum > 0)
31                         high --;
32                      else
33                         low ++;
34                 }
35             }
36         }
37         return res;
38     }

https://github.com/LuqiPan/LeetCode/blob/master/3Sum.java

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

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

        if (num.length < 3) {

            return result;

        }

        Arrays.sort(num);

        for (int i = 0 ; i < num.length - 2 ; i++) {

            if (i != 0 && num[i] == num[i-1]) { //\\

                continue;

            }

            int left = i + 1;

            int right = num.length - 1;

            while (left < right) {

                int sum = num[i] + num[left] + num[right];

                if (sum < 0) {

                    left++;

                } else if (sum > 0) {

                    right--;

                } else {

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

                    temp.add(num[i]);

                    temp.add(num[left]);

                    temp.add(num[right]);

                    result.add(temp);

                    do {

                        left++;

                    } while (left < right && num[left] == num[left-1]);

                    do {

                        right--;

                    } while (right > left && num[right] == num[right+1]);

                }

            }

        }

        return result;

    }

Use HashSet to remove duplicates - not good

 1     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

 2         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 3         if(num.length<3||num == null)
 4             return res;
 5         
 6         HashSet<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>();
 7         
 8         Arrays.sort(num);
 9         
10         for(int i = 0; i <= num.length-3; i++){
11             int low = i+1;
12             int high = num.length-1;
13             while(low<high){//since they cannot be the same one, low should not equal to high
14                 int sum = num[i]+num[low]+num[high];
15                 if(sum == 0){
16                     ArrayList<Integer> unit = new ArrayList<Integer>();
17                     unit.add(num[i]);
18                     unit.add(num[low]);
19                     unit.add(num[high]);
20                     
21                     if(!hs.contains(unit)){
22                         hs.add(unit);
23                         res.add(unit);
24                     }
25                     
26                     low++;
27                     high--;
28                 }else if(sum > 0)
29                     high --;
30                  else
31                     low ++;
32             }
33         }
34         
35         return res;
36     }

http://blog.csdn.net/linhuanmars/article/details/19711651

public ArrayList<ArrayList<Integer>> threeSum(int[] num)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null || num.length<=2)
        return res;
    Arrays.sort(num);
    for(int i=num.length-1;i>=2;i--)
    {
        if(i<num.length-1 && num[i]==num[i+1])
            continue;
         ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,-num[i]);
         for(int j=0;j<curRes.size();j++)
         {
             curRes.get(j).add(num[i]);
         }
         res.addAll(curRes);
    }
    return res;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int end,int target)
{
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if(num==null || num.length<=1)
        return res;
    int l = 0;
    int r = end;
    while(l<r)
    {
        if(num[l]+num[r]==target)
        {
            ArrayList<Integer> item = new ArrayList<Integer>();
            item.add(num[l]);
            item.add(num[r]);
            res.add(item);
            l++;
            r--;
            while(l<r&&num[l]==num[l-1])
                l++;
            while(l<r&&num[r]==num[r+1])
                r--;
        }
        else if(num[l]+num[r]>target)
        {
            r--;
        }
        else
        {
            l++;
        }
    }
    return res;
}

* The solution also does not handle duplicates. Therefore, it is not only time inefficient, but also incorrect.

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //sort array
        Arrays.sort(num);
 
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> each = new ArrayList<Integer>();
        for(int i=0; i<num.length; i++){
            if(num[i] > 0) break;
 
            for(int j=i+1; j<num.length; j++){
                if(num[i] + num[j] > 0 && num[j] > 0) break;
 
                for(int k=j+1; k<num.length; k++){
                  if(num[i] + num[j] + num[k] == 0) {
 
                      each.add(num[i]);
                      each.add(num[j]);
                      each.add(num[k]);
                      result.add(each);
                      each.clear();
                  }
                }
            }
        }
 
        return result;
    }

http://fisherlei.blogspot.com/2013/01/leetcode-3-sum-solution.html
Read full article from LeetCode – 3Sum