LeetCode 三数之和 — 改进解法
题目：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2] ]
最开始做的解法是先将整个数组排序；然后遍历前两个数(a和b)的所有情况(n^2)；对于第三个数，则从剩余的数中（即从第二个数下一个位置开始到末尾）利用二分查找出是否存在数字 -(a+b)即可。 复杂度O(n^2·logn) ：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
Map<Integer,Integer> mi = new HashMap();
for(int i=0;i<nums.length-1;i++) {
if(mi.get(nums[i]) != null) continue; //记录i下标读过的数字
mi.put(nums[i],1);
Map<Integer,Integer> mj = new HashMap();
for(int j=i+1;j<nums.length;j++) {
if(mj.get(nums[j]) != null) continue; //记录j下标读过的数字
mj.put(nums[j],1);
int temp = -(nums[i]+nums[j]);
if(bSearch(nums,j+1,nums.length-1,temp) == false) continue; //二分搜索j下标之后的区间是否有数字temp
ans.add(Arrays.asList(nums[i],nums[j],temp));
}
}
return ans;
}
//二分算法
public boolean bSearch(int[] nums,int s,int e,int key) {
int start=s,end=e,mid;
while(start<=end){
mid = (start+end)/2;
if(key < nums[mid]) end=mid-1;
else if(key > nums[mid]) start=mid+1;
else if(key == nums[mid]) return true;
}
return false;
}
}
里面有两个用了哈希的地方，所以时间复杂度应该还要乘上一个常数K...(解数组相关的题感觉总有些依赖哈希的方法=_= ...)
最近做了另一个数组区间相关的题目，受其解法的启发，打算对这道题解法进行优化。
还是先对数组进行排序；对第一个数字(a)进行遍历，而然后在剩余的数中用前后指针的方法找出两个和为-a的数字：两个指针left和right；left初始化为数字a的下一位置，right为最后一个位置。比较nums[left]+nums[right]+a和0的大小；如果大于0则right--，小于就left++。 其中在添加结果集时需考虑去重问题，用个哈希判断是否有重复就行了，复杂度O(n^2·K) ：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
Map<Integer,Integer> mi = new HashMap();
for(int i=0;i<nums.length-2;i++) {
if(mi.get(nums[i]) != null) continue; //记录i下标读过的数字
mi.put(nums[i],1);
Map<Integer,Integer> mj = new HashMap();
int l = i+1, r = nums.length-1, temp;
while(l<r) {
temp = nums[i] + nums[l] + nums[r];
if(temp < 0) {
l++;
} else if(temp > 0) {
r--;
} else {
if((mj.get(nums[l])) == null) {
ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
mj.put(nums[l], 1);
}
l++; r--;
}
}
}
return ans;
}
}