给定一个包含 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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 定义返回结果
List<List<Integer>> res=new ArrayList<>();
// 先排序
Arrays.sort(nums);
// 迭代，每次定位一个值，然后再使用快慢指针进行查找另外两个值
int i=0;
// 条件是因为每次都要三个指针，画图比较
while(i<nums.length-2){
// 找到其他两个值，使用双指针的方式
twoSum(nums,i,res);
// 去重
int temp=nums[i];
while(i<nums.length && nums[i]==temp){
i++;
}
}
return res;
}
private void twoSum(int[] nums,int i,List<List<Integer>> res){
// 定义双指针
int j=i+1;
int k=nums.length-1;
// 迭代
while(j < k){
if(nums[i]+nums[j]+nums[k] == 0){
res.add(Arrays.asList(nums[i],nums[j],nums[k]));
// 避免死循环并且去重
int temp=nums[j];
while(nums[j]==temp&& j<k){
j++;
}
}else if(nums[i]+nums[j]+nums[k] < 0){
j++;
}else{
k--;
}
}
}
}
二刷
class Solution {
// 每定位一个值，然后使用双指针去遍历
public List<List<Integer>> threeSum(int[] nums) {
// 定义返回结果
List<List<Integer>> list = new ArrayList<>();
// 先排序便于使用头尾双指针
Arrays.sort(nums);
// 迭代结束的条件是，需要保留三个指针的位置
int i=0;
while(i<nums.length-2){
// 定位一个值之后，剩余的目标值使用双指针去查找
int target = 0-nums[i];
// 使用双指针遍历
findTwoNums(list,target,i,nums);
// 这里也要去重
int temp = nums[i];
// 运算符前后的讲究（可以交换一下位置试试）
while(i<nums.length && temp == nums[i]){
i++;
}
}
return list;
}
// 查找其他两个值，双指针
private void findTwoNums(List<List<Integer>> list,int target,int i, int[] nums){
// 定义头尾指针
int head = i+1;
int tail = nums.length-1;
// 放在循环中，得到所有符合条件的值
while(head<tail){
// 因为是从小到大是排好序的，那么头尾双指针，就是大了尾向前移动；小了头指针向后移动
if(nums[head] + nums[tail] == target){
List<Integer> resList = new ArrayList<>();
resList.add(nums[head]);
resList.add(nums[tail]);
resList.add(nums[i]);
list.add(resList);
// 就这样不会去重
// head++;
// 这段主要是为了去重
int temp = nums[head];
while(nums[head]==temp && head<tail){
head++;
}
}
if(nums[head] + nums[tail] > target){
tail--;
}
if(nums[head] + nums[tail] < target){
head++;
}
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96219.html
