class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            twoSum(nums, i + 1, nums.length - 1, -nums[i], result);
        }
        return result;
    }

    public void twoSum(int[] numbers, int i, int j, int target, List<List<Integer>> result) {
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                result.add(Arrays.asList(-target, numbers[i], numbers[j]));
                while (i < j && numbers[i] == numbers[i+1]) i++;
                while (i < j && numbers[j] == numbers[j-1]) j--;
                i++; j--;
            }
            else if (sum > target) j--;
            else i++;
        }
    }
}