3Sum

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

Naive Way:这已经是我第三次做这道题了。 brute force是O(n^3)，然后较好的做法是O(n^2)。

经查证，还没有方法能在小于O(n^2)的时间内解决3sum问题。实际在OJ上做，发现即使是同样的O(n^2)

的run time, 也会有超时。

第一种做法, 一开始不排序，先用一个map记录每个数的出现次数，遍历O(n^2)求两两之和，再再map中

看看有没有剩下的那个数，这样的做法需要在形成list的时候排序，并且得有一个set控制duplicate。

但是这样的做法超时了。

public class Solution {

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

        Set<List<Integer>> set = new HashSet<List<Integer>>();

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        List<List<Integer>> output = new ArrayList<List<Integer>>();

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

            if(map.containsKey(num[i]))

                map.put(num[i], map.get(num[i])+1);

            else

                map.put(num[i], 1);

        }

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

            for(int j = i+1;j < num.length;j++){

                int a = num[i];

                int b = num[j];

                int c = -num[i]-num[j];

                if(map.containsKey(c)){

                    int count = 1;

                    count += a==c?1:0;

                    count += b==c?1:0;

                    if(count <= map.get(c)){

                        List<Integer> list = new ArrayList<Integer>();

                        int arr[] = new int[3];

                        arr[0] = a;

                        arr[1] = b;

                        arr[2] = c;

                        Arrays.sort(arr);

                        list.add(arr[0]);

                        list.add(arr[1]);

                        list.add(arr[2]);

                        if(!set.contains(list))

                            set.add(list);

                    }

                }

            }

        }

        output.addAll(set);

        return output;

    }

    

}

Improved Way: 
第二种做法，也是比较牛一点的做法，就是wiki上给的做法，但是这里要求去除重复，要做出修改。

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> rlst = new ArrayList<List<Integer>>();
        Arrays.sort(num);
        for(int u = 0;u < num.length-2;u++){
            if(u==0 || (u > 0 && num[u]!=num[u-1])){
            int i = u+1;
            int j = num.length-1;
            while(i < j){
                int sum = num[i]+num[j]+num[u];
                if(sum==0){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(num[u]);
                    list.add(num[i]);
                    list.add(num[j]);
                    rlst.add(list);
                    while(i < j){
                        if(num[j]!=num[j-1])
                            break;
                        j--;
                    }
                    while(i < j){
                        if(num[i]!=num[i+1])
                            break;
                        i++;
                    }
                    i++;
                    j--;
                }else if(sum > 0){
                    j--;
                }else{
                    i++;
                }
            }
            }
        }
        return rlst;
    }
}


最后我发现我第一次的做法，是可以通过的O(n^2)非常非常的厉害，我觉得，居然想到了用正数负数。

public class Solution {
    List<List<Integer>> output;
    HashSet<List<Integer>> visited;
    public List<List<Integer>> threeSum(int[] num) {
        output = new ArrayList<List<Integer>>();
        visited = new HashSet<List<Integer>>();
        //Arrays.sort(num);
        Map<Integer, Integer> positive = new HashMap<Integer, Integer>();
        Map<Integer, Integer> negative = new HashMap<Integer, Integer>();
        int numOfZeros = 0;
        // construct the mapping
        for(int i = 0;i < num.length;i++){
            if(num[i] == 0)
                numOfZeros++;
            if(num[i] > 0)
                if(positive.containsKey(num[i]))
                    positive.put(num[i], positive.get(num[i])+1);
                else
                    positive.put(num[i],1);
            if(num[i] < 0)
                if(negative.containsKey(num[i]))
                    negative.put(num[i], negative.get(num[i])+1);
                else
                    negative.put(num[i],1);
        }
       
        // generate results
        // two positive + one negative
        for(Map.Entry<Integer, Integer> a:positive.entrySet())
            for(Map.Entry<Integer, Integer> b:positive.entrySet())
                if(a.getKey() != b.getKey() || a.getValue() >= 2)
                    if(negative.containsKey(-a.getKey()-b.getKey()))
                        addResult(a.getKey(),b.getKey(),-a.getKey()-b.getKey());
                   
       
        // two negative + one positive
        for(Map.Entry<Integer, Integer> a:negative.entrySet())
            for(Map.Entry<Integer, Integer> b:negative.entrySet())
                if(a.getKey() != b.getKey() || a.getValue() >= 2)
                    if(positive.containsKey(-a.getKey()-b.getKey()))
                        addResult(a.getKey(),b.getKey(),-a.getKey()-b.getKey());
       
        // one positive+zero+one negative
        if(numOfZeros > 0)
            for(Map.Entry<Integer, Integer> a:negative.entrySet())
                if(positive.containsKey(-a.getKey()))
                    addResult(0,a.getKey(),-a.getKey());
       
        // three zeros
        if(numOfZeros > 2)
            addResult(0,0,0);
           
        return output;
    }
   
    private void addResult(int a, int b, int c){
        int array[] = {a,b,c};
        Arrays.sort(array);
        List<Integer> result = new ArrayList<Integer>();
        result.add(array[0]);
        result.add(array[1]);
        result.add(array[2]);
        if(!visited.contains(result)){
            visited.add(result);
            output.add(result);
        }
    }
}