Lintcode - 3Sum

Given an arrayS_of n integers, are there elements_a,b,_c_in_S_such thata + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice

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.

Example

For example, given array S ={-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

Analysis: A straightforward solution is to have three nesting loops and once a result is found, save it to hashMap to avoid duplicates. A better solution is to simplify the issue to a 2sum issue.

Solution 1

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {        
    ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
    if (numbers.length == 0){
    return results;
    }

    Arrays.sort(numbers);        
    HashMap<Integer, List<Integer>> visited = new HashMap<Integer, List<Integer>>();

    int right = numbers.length - 1;
    for (int i = 0; i < right; i++){
        for (int j = i + 1; j < right; j++){                
            if (visited.containsKey(numbers[i]) && visited.get(numbers[i]).contains(numbers[j])){
                continue;
        }
            int subsum = numbers[i] + numbers[j];
            int index = right;
            while(index > j){
                if (subsum + numbers[index] == 0){                        
                    ArrayList<Integer> result = new ArrayList<Integer>();                        
                    result.addAll(Arrays.asList(numbers[i], numbers[j], numbers[index]));    

                    List<Integer> v = new ArrayList<Integer>();
                    if (visited.containsKey(numbers[i])){
                        v = visited.get(numbers[i]);
                    }
                    v.add(numbers[j]);
                    visited.put(numbers[i], v);
                    results.add(result);
                    while (j < right && numbers[j] == numbers[j+1]){
                        j++;
                    }
                    break;
                }
                index--;
            }
        }
    }
    return results;
}

Solution 2. A better Solution.

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
    if (numbers.length == 0) {
        return results;
    }

    Arrays.sort(numbers);

    for (int i = 0; i < numbers.length - 1; i++) {
        results.addAll(twoSum(numbers, i + 1, numbers.length - 1, 0 - numbers[i]));
        if (numbers[i] == -3){
            int a = 0;
            a =3;
        }
        while (i < numbers.length - 1 && numbers[i] == numbers[i + 1]) {
            i++;
        }
    }
    return results;
}

public ArrayList<ArrayList<Integer>> twoSum(int[] numbers, int left, int right, int target) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    while (left < right) {
        if (numbers[left] + numbers[right] == target) {
            ArrayList<Integer> subresult = new ArrayList<Integer>();
            subresult.add(-target);

            if (-target == -3){
                int a = 0;
                a =3;
            }
            subresult.add(numbers[left]);
            subresult.add(numbers[right]);
            result.add(subresult);
            while (left < right && numbers[left] == numbers[++left]);
            while (left < right && numbers[right] == numbers[--right]);

        } else if (numbers[left] + numbers[right] < target) {
            left++;
        } else {
            right--;
        }
    }

    return result;
}