3Sum

Java

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 List<List<Integer>> threeSum(int[] numbers) {
        // write your code here
        List<List<Integer>> result = new ArrayList<>();
        if(numbers == null || numbers.length < 3){
            return result;
        }
        Arrays.sort(numbers);
        
        for(int i = 2; i < numbers.length; i++){
            if(i + 1 < numbers.length && numbers[i + 1] == numbers[i]){
                continue;
            }
            int tgt = -1 * numbers[i];
            twoSum(numbers, tgt, i, result);
        }
        return result;
    }
    public void twoSum(int[] nums, int target, int r, List<List<Integer>> result) {
        // write your code here
        int left = 0;
        int right = r - 1;
        while(left < right){
            if(nums[left] + nums[right] == target){
                List<Integer> temp = new ArrayList<>();
                temp.add(-1*target);
                temp.add(nums[left]);
                temp.add(nums[right]);
                Collections.sort(temp);
                result.add(temp);
                left++;
                right--;
                while(left < right && nums[left] == nums[left-1]){
                    left++;
                }
                while(left < right && nums[right] == nums[right+1]){
                    right--;
                }
            }else if(nums[left] + nums[right] < target){
                left++;
            }else{
                right--;
            }
        }
    }
}