原题重述:(点击图片可以进入来源链接)
这到题目的中文解释是,
输入一个数组,例如{-1 0 1 2 -1 -4},从数组中找三个数(a,b,c),使得其和0,输出所有的(a,b,c)组合。
要求abc不能重复,并且a<=b<=c。
拿到这个题目的时候,其实每个程序猿都能想到如下的算法,也就是暴力破解,其时间复杂度为o(n^3):
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
for(int k=j+1;k<nums.length;j++){
if(nums[i]+nums[j]+nums[k]==0){
addResult(nums[i], nums[j], nums[k]);
}
}
}
}
首先需要对输入的数组进行排序,这样的话由于上面的i<j<k,所以可以保证nums[i]<nums[j]<nums[k]。
其实我的算法的思路就是在暴力破解的基础上进行优化,尽量降低时间复杂度。
在java中对数组排序的方法是:Arrays.sort(nums);
第三个循环其实是没有必要的,因为在确定了i,j的值之后,需要寻找的nums[k]的值就已经确定了,即-(nums[i]+nums[j])。
因此无需循环,只需要判断数组剩下的元素中是否存在这个值就可以了。
基于这个思路我构建了一个hashmap作为hash索引表,用于查找每个值出现的位置:(考虑到一个值可能出现在多个位置的情况,用arraylist)
因为nums是已经排序过的,所以索引表中的arraylist也是已排序好的。
HashMap<Integer, ArrayList<Integer>> index = new HashMap<>();
构建这个索引表的代码如下:
for(int i=0;i<nums.length;i++){
int num = nums[i];
if(num==0){
n++;
}
if(index.get(num)==null){ index.put(num, new ArrayList<Integer>());
} index.get(num).add(i); }
这里面的n是表示0的个数,如果n>=3,就直接输出一个[0 0 0]了。
从索引表查询需要的数的方式,我想了很久,最后想到一个很不错的方法:
int p = -(nums[i]+nums[j]);
if(p<0) continue;
ArrayList<Integer> in = index.get(p);
if(in==null) continue;
if(in.get(in.size()-1)>j){
if(p>nums[j]){
addResult(nums[i], nums[j],p);
}else if(p>nums[i]){
addResult(nums[i], p,nums[j]);
}else{
addResult(p,nums[i], nums[j]);
} }
第2行,为什么要舍弃p<0的情况?因为要避免重复。如果p也是负数的话,由于nums[i]<nums[j]那么会出现两种情况:
①nums[i]和nums[j]都是正数;
②nums[i]是负数,nums[j]是正数 。
那么在其他的扫描过程中一定会出现:
①那时的nums[i]'=p,p'=nums[i],nums[j]'=nums[j];
②那时的p'=nums[j],nums[i]'=min(nums[i],p),nums[j]'=max(nums[i],p)。
第5行in.get(in.size()-1)>j是什麼意思?
我们这个时候是需要找一个k(k>j),使得nums[k]=p,如果有就输出nums[k]。
ArrayList in表示使得nums[k]=p的所有k值,如果最大的k值大于j,那不就表示存在k>j,使得nums[k]=p了吗?
一定要求k>j,因为如下的情况是不符合要求的:
输入 [-1 0 1 2] 不能输出 [-1 -1 2] 因为-1的索引是[0],在遍历时它不满足k>j
关于避免重复的问题,
我用addResult函数来避免重复,大家一看应该就懂
HashSet<String> repeat = new HashSet<String>(); // 查重
List<List<Integer>> result = new LinkedList<List<Integer>>(); public void addResult(int n1, int n2, int n3) {
String s = n1 + "&"+n2; if (!repeat.contains(s)) {
List<Integer> p = new ArrayList<>();
p.add(n1);
p.add(n2);
p.add(n3);
result.add(p);
repeat.add(s);
}
}
最终详细的代码如下:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List; /**
* 优化了的o(n^2) 3sum算法
* @author user
*
*/
public class Solution {
HashSet<String> repeat = new HashSet<String>(); // 查重
List<List<Integer>> result = new LinkedList<List<Integer>>(); public void addResult(int n1, int n2, int n3) {
String s = n1 + "&"+n2; if (!repeat.contains(s)) {
List<Integer> p = new ArrayList<>();
p.add(n1);
p.add(n2);
p.add(n3);
result.add(p);
repeat.add(s);
}
} public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3) {
return result;
}
Arrays.sort(nums);
if (nums.length == 3) {
if (nums[0] + nums[1] + nums[2] == 0) { addResult(nums[0], nums[1], nums[2]);
return result;
} else {
return result;
}
}
HashMap<Integer, ArrayList<Integer>> index = new HashMap<>();
int n=0; for(int i=0;i<nums.length;i++){
int num = nums[i];
if(num==0){
n++;
}
if(index.get(num)==null){ index.put(num, new ArrayList<Integer>());
} index.get(num).add(i); }
if(n>=3) addResult(0, 0, 0); for(int i=0;i<nums.length;i++){
if((nums[i]<0&&nums[nums.length-1]<-i)||(nums[i]>0&&nums[0]>-nums[i])) continue; for(int j=i+1;j<nums.length;j++){ int p = -(nums[i]+nums[j]); if(p<0) continue;
ArrayList<Integer> in = index.get(p);
if(in==null) continue;
if(in.get(in.size()-1)>j){
if(p>nums[j]){
addResult(nums[i], nums[j],p);
}else if(p>nums[i]){
addResult(nums[i], p,nums[j]);
}else{
addResult(p,nums[i], nums[j]);
} } } } return result;
} public static void main(String[] args) {
long m = System.currentTimeMillis();
int a[] = {-1,-2,-3,4,1,3,0,3,-2,1,-2,2,-1,1,-5,4,-3}; Solution solution = new Solution();
System.out.println(solution.threeSum(a).size()); long n = System.currentTimeMillis();
System.out.println(n - m); } }