LeetCode刷题Java版015.三数之和
作者：沉默王二
发布时间：2022-07-30T16:58:06.590+0800
015.三数之和
题意
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
难度
中等
示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
分析
我们之前做过 001.两数之和 这道题，两道题非常相似，虽然各有各的特点，我们却可以从中得到启发，只要将 a + b + c = 0 转移成 a + b = -c 似乎就能套用之前的解题方法，但很遗憾，我们没办法做到，因为目标的值（也就是 -c）一直在改变，两数之和的时候是固定的，所以我们另寻出路。
首先，我们知道这种从 …… 中选 …… 出来的题目，顺序对答案没有影响，所以我们不妨先将整个数组进行排序。
排序后，我们就能得到一个从小到大排列好的数组，这时候我们只需要定一移二就能找出答案了，也就是将a + b + c = 0中的a确定了，再移动后面两个数来获得相应的组合。
但是这样子的时间复杂度是，太大了，不现实。
怎么办呢？
先前做的排序就派上用场了。这时候a确定了，那么我们只要确定b、c即可，首先让lef = i + 1,rig = n - 1（a = nums[i]、b = nums[lef]、c = nums[rig]）如果a + b + c < 0，那么如果rig下标向左移动，就会让a + b + c变得更小，肯定不行，于是我们移动lef，让b变大，从而让a + b + c靠近0。a + b + c > 0也是同理，移动rig，让a + b + c减小，从而靠近0。
public class Solution {
public List<List
List<List
Arrays.sort (nums);
for(int i = 0;i < nums.length ;i++){
if( i > 0 && nums[i] == nums[i - 1])
continue;
if(nums[i] > 0)
break;
int lef = i + 1;
int rig = nums.length - 1;
while(lef < rig){
if(nums[i] + nums[lef] + nums[rig] < 0)
lef++;
else{
if(nums[i] + nums[lef] + nums[rig] == 0){
res.add (Arrays.asList(nums[i],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;
lef++;
}
rig--;
}
}
}
return res;
}
}
注意题解中的一个细节，就是我们需要去重，防止重复的三元组出现，每次选择一个lef或者rig，都需要移动到下一个不同的位置处。
总结
本次我们采用定一移二的方法，将整个数组排序后，利用其有序性，巧妙地排除了很多不可能的答案，从而将时间复杂度从降为。我们在面对这一系列（从一些元素中选出几个）的时候，他们之间的顺序关系往往是不影响结果的，那么我们就可以将其排序，再仔细观察，有时解题的关键就藏于其中。
力扣链接：https://leetcode.cn/problems/3sum/
015.三数之和
题意
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
难度
中等
示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
分析
我们之前做过 001.两数之和 这道题，两道题非常相似，虽然各有各的特点，我们却可以从中得到启发，只要将 a + b + c = 0 转移成 a + b = -c 似乎就能套用之前的解题方法，但很遗憾，我们没办法做到，因为目标的值（也就是 -c）一直在改变，两数之和的时候是固定的，所以我们另寻出路。
首先，我们知道这种从 …… 中选 …… 出来的题目，顺序对答案没有影响，所以我们不妨先将整个数组进行排序。
排序后，我们就能得到一个从小到大排列好的数组，这时候我们只需要定一移二就能找出答案了，也就是将a + b + c = 0中的a确定了，再移动后面两个数来获得相应的组合。
但是这样子的时间复杂度是，太大了，不现实。
怎么办呢？
先前做的排序就派上用场了。这时候a确定了，那么我们只要确定b、c即可，首先让lef = i + 1,rig = n - 1（a = nums[i]、b = nums[lef]、c = nums[rig]）如果a + b + c < 0，那么如果rig下标向左移动，就会让a + b + c变得更小，肯定不行，于是我们移动lef，让b变大，从而让a + b + c靠近0。a + b + c > 0也是同理，移动rig，让a + b + c减小，从而靠近0。
public class Solution {
public List<List
List<List
Arrays.sort (nums);
for(int i = 0;i < nums.length ;i++){
if( i > 0 && nums[i] == nums[i - 1])
continue;
if(nums[i] > 0)
break;
int lef = i + 1;
int rig = nums.length - 1;
while(lef < rig){
if(nums[i] + nums[lef] + nums[rig] < 0)
lef++;
else{
if(nums[i] + nums[lef] + nums[rig] == 0){
res.add (Arrays.asList(nums[i],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;
lef++;
}
rig--;
}
}
}
return res;
}
}
注意题解中的一个细节，就是我们需要去重，防止重复的三元组出现，每次选择一个lef或者rig，都需要移动到下一个不同的位置处。
总结
本次我们采用定一移二的方法，将整个数组排序后，利用其有序性，巧妙地排除了很多不可能的答案，从而将时间复杂度从降为。我们在面对这一系列（从一些元素中选出几个）的时候，他们之间的顺序关系往往是不影响结果的，那么我们就可以将其排序，再仔细观察，有时解题的关键就藏于其中。
力扣链接：https://leetcode.cn/problems/3sum/
015.三数之和
题意
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
难度
中等
示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
分析
我们之前做过 001.两数之和 这道题，两道题非常相似，虽然各有各的特点，我们却可以从中得到启发，只要将 a + b + c = 0 转移成 a + b = -c 似乎就能套用之前的解题方法，但很遗憾，我们没办法做到，因为目标的值（也就是 -c）一直在改变，两数之和的时候是固定的，所以我们另寻出路。
首先，我们知道这种从 …… 中选 …… 出来的题目，顺序对答案没有影响，所以我们不妨先将整个数组进行排序。
排序后，我们就能得到一个从小到大排列好的数组，这时候我们只需要定一移二就能找出答案了，也就是将a + b + c = 0中的a确定了，再移动后面两个数来获得相应的组合。
但是这样子的时间复杂度是，太大了，不现实。
怎么办呢？
先前做的排序就派上用场了。这时候a确定了，那么我们只要确定b、c即可，首先让lef = i + 1,rig = n - 1（a = nums[i]、b = nums[lef]、c = nums[rig]）如果a + b + c < 0，那么如果rig下标向左移动，就会让a + b + c变得更小，肯定不行，于是我们移动lef，让b变大，从而让a + b + c靠近0。a + b + c > 0也是同理，移动rig，让a + b + c减小，从而靠近0。
public class Solution {
public List<List
List<List
Arrays.sort (nums);
for(int i = 0;i < nums.length ;i++){
if( i > 0 && nums[i] == nums[i - 1])
continue;
if(nums[i] > 0)
break;
int lef = i + 1;
int rig = nums.length - 1;
while(lef < rig){
if(nums[i] + nums[lef] + nums[rig] < 0)
lef++;
else{
if(nums[i] + nums[lef] + nums[rig] == 0){
res.add (Arrays.asList(nums[i],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;
lef++;
}
rig--;
}
}
}
return res;
}
}
注意题解中的一个细节，就是我们需要去重，防止重复的三元组出现，每次选择一个lef或者rig，都需要移动到下一个不同的位置处。
总结
本次我们采用定一移二的方法，将整个数组排序后，利用其有序性，巧妙地排除了很多不可能的答案，从而将时间复杂度从降为。我们在面对这一系列（从一些元素中选出几个）的时候，他们之间的顺序关系往往是不影响结果的，那么我们就可以将其排序，再仔细观察，有时解题的关键就藏于其中。
力扣链接：https://leetcode.cn/problems/3sum/
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412