public static void main(String[] args) {

Solution solution = new P15ThreeSum().new Solution();

int[] nums = new int[]{-1, 0, 1, 2, -1, -4};

solution.threeSum(nums);

// TO TEST

}

//leetcode submit region begin(Prohibit modification and deletion)

class Solution {

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

if (nums.length == 0) {

return new ArrayList<>();

}

int target = 0;

Arrays.sort(nums);

List<List<Integer>> res = new LinkedList<>();

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

List<List<Integer>> result = twoSum(nums, i + 1, target - nums[i]);

for (List<Integer> list : result) {

list.add(nums[i]);

res.add(list);

}

while (i < (nums.length - 1) && nums[i + 1] == nums[i]) i++;

}

return res;

}

public List<List<Integer>> twoSum(int[] nums, int start, int target) {

int left = start, right = nums.length - 1;

List<List<Integer>> result = new LinkedList<>();

while (left < right) {

int sum = nums[left] + nums[right];

int leftNum = nums[left];

int rightNum = nums[right];

if (sum < target) {

while (left < right && leftNum == nums[left]) left++;

} else if (sum > target) {

while (left < right && rightNum == nums[right]) right--;

} else {

LinkedList<Integer> list = new LinkedList<>();

list.add(nums[left]);

list.add(nums[right]);

result.add(list);

while (left < right && leftNum == nums[left]) left++;

while (left < right && rightNum == nums[right]) right--;

}

}

return result;

}

}

}