给你一个包含 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]
输出:[]
提示:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
方式一:通过Set集合进行判断
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list=new ArrayList<>();
if(nums.length<3) return list;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
//如果排序后的首个元素大于0,则后面的元素都大于0,不存在3个数之和为0
if(nums[i]>0) break;
//第一个数
int first=nums[i];
//排除重复的数
if(i>0&&nums[i]==nums[i-1]) continue;
Set<Integer> set=new HashSet<>();//放到外循环中,每次循环都重新创建set集合
for(int j=i+1;j<nums.length;j++){
//第三个数
int third=nums[j];
int second=-(first+third);//第一个数和第二个数加和取反为第三个数
if(set.contains(second)){
//Arrays.asList()将数组转化为List集合
list.add(new ArrayList<>(Arrays.asList(first,third,-(first+third))));
while(j < nums.length - 1 && nums[j] == nums[j + 1]) j++;//去重
}
set.add(third);//将第三个数存入集合中,因为第三个数是数组中原有的数,用它与second进行比较,而不能将second存到set中
}
}
return list;
}
}
方式二:双指针
ublic class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list=new ArrayList<>();
//判空,以及判断数组长度是否小于3
if(nums==null || nums.length<3) return list;
Arrays.sort(nums); //排序
for(int i=0;i<nums.length-1;i++){
if(nums[i]>0) break;//如果排序后的首个元素大于0,则后面的元素都大于0,不存在3个数之和为0
if(i>0 && nums[i]==nums[i-1]) continue; //过滤重复项
int middle=-nums[i];
//定义双指针
int left=i+1,right=nums.length-1;
while(left<right){
if(nums[left]+nums[right]>middle){//说明选用的正数太大,右指针应向左移动
right--;
}else if(nums[left]+nums[right]<middle){//说明负数太小,left应向右移动
left++;
}else{ //ums[left]+nums[right]==middle
list.add(new ArrayList<>(Arrays.asList(nums[left],nums[i],nums[right])));//Arrays.asList()将数组转化为List集合
//指针继续移动
left++;
right--;
while(left<right && nums[left]==nums[left-1]) left++;//去重
while(left<right && nums[right]==nums[right+1]) right--;
}
}
}
return list;
}
public static void main(String[] args) {
Solution s=new Solution();
System.out.println(s.threeSum(new int[]{-1,0,1,2,-1,-4}));
}
}