题目概述:给定一数组nums,以及三元组的定义:i!=j,j!=k,k!=i,并且nums[i] + nums[j] + nums[k] = 0。返回该数组中所有的三元组,{1,0,-1},{-1,0,1}视为同一个三元组
解题思路:由于数据范围比较小,直接采用二重循环加二分的思路,找到符合的三元组,再通过set集合去重。由于我集合还不是用的很习惯,代码写的可能比较复杂。去重具体步骤:在本题中用set去重的关键是需要让类似{1,0,-1},{-1,0,1}这样的数组视为相同数组。我的做法是对这些数组进行排序处理。通过本题可以知道,set底层在判定两个集合是否相同时,是通过遍历两个集合判断相同位置处的元素值是否一致实现的。
时间复杂度:\(O(n^2log(n))\)
代码:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
Set<List<Integer>> set = new HashSet<>();
for(int i = 0; i < n; i ++){
for(int j = i + 1; j < n; j ++){
int t = nums[i] + nums[j];
int pos = find(nums,-t);
if(pos == -1 || pos == i || pos == j)continue;
else{
//去重
int array[] = new int[3];
array[0] = nums[i];
array[1] = nums[j];
array[2] = nums[pos];
Arrays.sort(array);
List<Integer> list = new ArrayList<>();
for(int k = 0; k < 3; k ++)list.add(array[k]);
set.add(list);
}
}
}
return new ArrayList<List<Integer>>(set);
}
//二分
public int find(int nums[],int x){
int n = nums.length - 1;
int l = 0,r = n;
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] >= x)r = mid;
else l = mid + 1;
}
if(nums[l] == x)return l;
else return -1;
}
}