文章目录
题目：
给你一个包含 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
-10^5 <= nums[i] <= 10^5
解法1：双指针
/**
* 思路：
* 对数组进行排序，方便我们后续找不重复的三元组
* 我们可以先确定一个数，之后去找后两个数
* 遍历数组
* 如果当前的下标是0，或者当前下标i和前一个数不同进行循环。相同则找下一个数
* 确定另外两个数l和r
* 如果sum大于0，要让数接近0，必须让sum变小，移动右侧。
* 小于0，反之。
* 如果等于0就放入结果集result
* 之后判断l和r是否有重复值，进行移动
* 最后一起移动l和r（不可能有重复组合等于0，2个一起移动，当然移动一个也可以）
*/
public static List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i == 0 || nums[i] != nums[i - 1]) {
int l = i + 1, r = nums.length - 1;
while (r > l) {
int sum = nums[i] + nums[l] + nums[r];
if (sum > 0) {
r--;
} else if (sum < 0) {
l++;
} else {
result.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (r > l && nums[l] == nums[++l]) {
}
while (r > l && nums[r] == nums[--r]) {
}
}
}
}
}
return result;
}
时间复杂度：On^2
空间复杂度：On
解法2：Hash
/**
* 思路：
* 把三数和转换成两数和
* 2层for，已知2数和，寻找最后一个数，使得3数和为0
* 判断map中是否有所需值，有则进行记录
* 先对3个数进行排序，在放入set去重（防止相同元素不同位置的数组出现）
* 没有则把当前数放入map中
*/
public static List<List<Integer>> threeSum(int[] nums) {
HashSet<List<Integer>> set = new HashSet<>();
for (int i=0;i<nums.length-2;i++){
HashMap<Integer, Integer> map = new HashMap<>();
for (int j=i+1;j<nums.length;j++){
int need=-(nums[i]+nums[j]);
if (map.containsKey(need)){
List<Integer> list = Arrays.asList(nums[i], nums[j], need);
Collections.sort(list);
set.add(list);
}else {
map.put(nums[j], nums[j]);
}
}
}
return new ArrayList<>(set);
}
时间复杂度：On^2logn
空间复杂度：On
解法3：暴力
/**
* 思路：
* 遍历所有可能，找到3数和为0
* 进行排序之后用set进行去重，放入结果集
*/
public List<List<Integer>> threeSum(int[] nums) {
HashSet<List<Integer>> set = new HashSet<>();
for (int i=0;i<nums.length-2;i++){
for (int j=i+1;j<nums.length-1;j++){
for (int k=j+1;k<nums.length;k++){
if (nums[i]+nums[j]+nums[k]==0){
//排序后存放在set中的集合能保证没有重复
List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(list);
set.add(list);
}
}
}
}
return new ArrayList<>(set);
}
时间复杂度：On^3
空间复杂度：On