题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
第一次提交的代码
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Map<Integer,Integer> map=new HashMap<>();
Set<Set<Integer>> set = new HashSet<>();
List<List<Integer>> result=new ArrayList<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
int minus=0-(nums[i]+nums[j]);
if(map.get(minus)!=null&&(map.get(minus)!=i&&map.get(minus)!=j)){
Set<Integer> tempSet=new HashSet<>(Arrays.asList(nums[i],nums[j],minus));
if(!set.contains(tempSet)){
result.add(Arrays.asList(nums[i],nums[j],minus));
set.add(tempSet);
}
}
}
}
return result;
}
}
时间复杂度也是O(n^2)，但是提交的时候显示超出时间限制，个人纳闷看了一下大神的解法，也是这个时复，感觉上像是我这里用了Set来去重耗费时间太久了还是怎么样？实在没弄清楚。
学习到的东西
大神的方法用的是双指针法(根本想不到用这个，还在想用哈希法来解决问题呢...)
因为我语言表达太难，大佬有图可以帮助理解，具体的链接我放在这(偷个懒)：
三数相加--Carl大佬
最终的代码
mport java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int left=0;
int right=0;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0)return result;
//对A去重
if(i>0&&nums[i-1]==nums[i])continue;
left=i+1;
right=nums.length-1;
while(left<right){
if((nums[i]+nums[left]+nums[right])>0)right--;
else if((nums[i]+nums[left]+nums[right])<0)left++;
else{
//三数之和正好等于0
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
//对B和C去重
while(left<right&&nums[left+1]==nums[left])left++;
while(left<right&&nums[right-1]==nums[right])right--;
left++;
right--;
}
}
}
return result;
}
}