package com.leetcode.array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
/**
* 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？
* 请你找出所有和为 0 且不重复的三元组。
*
* 注意：答案中不可以包含重复的三元组。
*
*
*
* 示例 1：
*
* 输入：nums = [-1,0,1,2,-1,-4]
* 输出：[[-1,-1,2],[-1,0,1]]
* 示例 2：
*
* 输入：nums = []
* 输出：[]
* 示例 3：
*
* 输入：nums = [0]
* 输出：[]
*
* 链接：https://leetcode-cn.com/problems/3sum
* @param nums
* @return
*/
public List> threeSum(int[] nums) {
List> ans = new ArrayList();
if(nums==null||nums.length<3) return ans;
int len = nums.length;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L 0) R--;
}
}
return ans;
}
}