3 Sum

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.

Have you met this question in a real interview? 

Yes

Example

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

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

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.

public class Solution {

    /**

     * @param numbers : Give an array numbers of n integer

     * @return : Find all unique triplets in the array which gives the sum of zero.

     */

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

        // write your code here

        if(numbers == null || numbers.length <= 2) return null;

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

        Arrays.sort(numbers);

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

            if(i > 0 && numbers[i] == numbers[i-1])

                continue;

            int j = i + 1, k = numbers.length - 1;

            while(j < k){

                if(j > i + 1 && numbers[j] == numbers[j-1]){

                    j++;

                    continue;

                } 

                if(numbers[i] + numbers[j] + numbers[k] == 0){

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

                    sub.add(numbers[i]);

                    sub.add(numbers[j]);

                    sub.add(numbers[k]);

                    res.add(sub);

                    j++; k--;

                } else if(numbers[i] + numbers[j] + numbers[k] > 0) k--;

                else j++;

            }

        }

        return res;

    }

}