题目描述
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
代码
先排序,然后一重循环套一个双指针求和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for(int i=0; i<n-2; i++){
if(i>0 && nums[i]==nums[i-1]) continue; //去除重复的
int tar = -nums[i];
//双指针枚举nums[j]+nums[k]的和
for(int j=i+1, k=n-1; j<n; j++){
if(j>i+1 && nums[j]==nums[j-1]) continue; //去除重复的aab
while(k>j && nums[j]+nums[k]>tar) k--;
if(j>=k) break;
if(nums[j]+nums[k]==tar){
List<Integer> list = new ArrayList<>();
list.add(nums[i]); list.add(nums[j]); list.add(nums[k]);
ans.add(list);
}
}
}
return ans;
}
}