这道题要求跟3Sum差不多，只是需求扩展到四个的数字的和了。我们还是可以按照3Sum中的解法，只是在外面套一层循环，相当于求n次3Sum。我们知道3Sum的时间复杂度是O(n^2)，所以如果这样解的总时间复杂度是O(n^3)。代码如下：
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(num==null||num.length==0)
return res;
Arrays.sort(num);
for(int i=num.length-1;i>2;i--)
{
if(i==num.length-1 || num[i]!=num[i+1])
{
ArrayList<ArrayList<Integer>> curRes = threeSum(num,i-1,target-num[i]);
for(int j=0;j<curRes.size();j++)
{
curRes.get(j).add(num[i]);
}
res.addAll(curRes);
}
}
return res;
}
private ArrayList<ArrayList<Integer>> threeSum(int[] num, int end, int target)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
for(int i=end;i>1;i--)
{
if(i==end || num[i]!=num[i+1])
{
ArrayList<ArrayList<Integer>> curRes = twoSum(num,i-1,target-num[i]);
for(int j=0;j<curRes.size();j++)
{
curRes.get(j).add(num[i]);
}
res.addAll(curRes);
}
}
return res;
}
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int end, int target)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
int l=0;
int r=end;
while(l<r)
{
if(num[l]+num[r]==target)
{
ArrayList<Integer> item = new ArrayList<Integer>();
item.add(num[l]);
item.add(num[r]);
res.add(item);
l++;
r--;
while(l<r&&num[l]==num[l-1])
l++;
while(l<r&&num[r]==num[r+1])
r--;
}
else if(num[l]+num[r]>target)
{
r--;
}
else
{
l++;
}
}
return res;
}
上述这种方法比较直接，根据3Sum的结果很容易进行推广。那么时间复杂度能不能更好呢？其实我们可以考虑用二分法的思路，如果把所有的两两pair都求出来，然后再进行一次Two Sum的匹配，我们知道Two Sum是一个排序加上一个线性的操作，并且把所有pair的数量是O((n-1)+(n-2)+...+1)=O(n(n-1)/2)=O(n^2)。所以对O(n^2)的排序如果不用特殊线性排序算法是O(n^2*log(n^2))=O(n^2*2logn)=O(n^2*logn)，算法复杂度比上一个方法的O(n^3)是有提高的。思路虽然明确，不过细节上会多很多情况要处理。首先，我们要对每一个pair建一个数据结构来存储元素的值和对应的index，这样做是为了后面当找到合适的两对pair相加能得到target值时看看他们是否有重叠的index，如果有说明它们不是合法的一个结果，因为不是四个不同的元素。接下来我们还得对这些pair进行排序，所以要给pair定义comparable的函数。最后，当进行Two Sum的匹配时因为pair不再是一个值，所以不能像Two Sum中那样直接跳过相同的，每一组都得进行查看，这样就会出现重复的情况，所以我们还得给每一个四个元素组成的tuple定义hashcode和相等函数，以便可以把当前求得的结果放在一个HashSet里面，这样得到新结果如果是重复的就不加入结果集了。
代码如下：
public class Node
{
int index;
int value;
public Node(int index, int value)
{
this.index = index;
this.value = value;
}
}
public class Pair
{
Node[] nodes;
public Pair(Node n1, Node n2)
{
nodes = new Node[2];
nodes[0] = n1;
nodes[1] = n2;
}
public int getSum()
{
return nodes[0].value+nodes[1].value;
}
}
public class Tuple
{
ArrayList<Integer> num;
public Tuple(ArrayList<Integer> num)
{
this.num = new ArrayList<Integer>(num);
Collections.sort(this.num);
}
public int hashCode() {
int hashcode = 5;
for(int i=0;i<this.num.size();i++)
{
hashcode = 31*hashcode + this.num.get(i);
}
return hashcode;
}
public boolean equals(Object obj) {
if (obj == null)
return false;
if (obj == this)
return true;
if (!(obj instanceof Tuple))
return false;
Tuple rhs = (Tuple) obj;
for(int i=0;i<this.num.size();i++)
{
if(!this.num.get(i).equals(rhs.num.get(i)))
{
return false;
}
}
return true;
}
}
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
ArrayList<Pair> pairs = getPairs(num);
Comparator<Pair> pairComparator = new Comparator<Pair>(){
@Override
public int compare(Pair p1, Pair p2){
return p1.getSum()-p2.getSum();
}
};
Collections.sort(pairs, pairComparator);
return twoSum(pairs, target);
}
private ArrayList<Pair> getPairs(int[] num)
{
ArrayList<Pair> res = new ArrayList<Pair>();
for(int i=0;i<num.length-1;i++)
{
Node n1 = new Node(i,num[i]);
for(int j=i+1;j<num.length;j++)
{
Node n2 = new Node(j,num[j]);
Pair pair = new Pair(n1,n2);
res.add(pair);
}
}
return res;
}
private ArrayList<ArrayList<Integer>> twoSum(ArrayList<Pair> pairs, int target){
HashSet<Tuple> hashSet = new HashSet<Tuple>();
int l = 0;
int r = pairs.size()-1;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
while(l<r){
if(pairs.get(l).getSum()+pairs.get(r).getSum()==target)
{
int lEnd = l;
int rEnd = r;
while(lEnd<rEnd && pairs.get(lEnd).getSum()==pairs.get(lEnd+1).getSum())
{
lEnd++;
}
while(lEnd<rEnd && pairs.get(rEnd).getSum()==pairs.get(rEnd-1).getSum())
{
rEnd--;
}
for(int i=l;i<=lEnd;i++)
{
for(int j=r;j>=rEnd;j--)
{
if(check(pairs.get(i),pairs.get(j)))
{
ArrayList<Integer> item = new ArrayList<Integer>();
item.add(pairs.get(i).nodes[0].value);
item.add(pairs.get(i).nodes[1].value);
item.add(pairs.get(j).nodes[0].value);
item.add(pairs.get(j).nodes[1].value);
//Collections.sort(item);
Tuple tuple = new Tuple(item);
if(!hashSet.contains(tuple))
{
hashSet.add(tuple);
res.add(tuple.num);
}
}
}
}
l = lEnd+1;
r = rEnd-1;
}
else if(pairs.get(l).getSum()+pairs.get(r).getSum()>target)
{
r--;
}
else{
l++;
}
}
return res;
}
private boolean check(Pair p1, Pair p2)
{
if(p1.nodes[0].index == p2.nodes[0].index || p1.nodes[0].index == p2.nodes[1].index)
return false;
if(p1.nodes[1].index == p2.nodes[0].index || p1.nodes[1].index == p2.nodes[1].index)
return false;
return true;
}
第二种方法比第一种方法时间上还是有提高的，其实这道题可以推广到k-Sum的问题，基本思想就是和第二种方法一样进行二分，然后两两结合，不过细节就非常复杂了（这点从上面的第二种解法就能看出来），所以不是很适合在面试中出现，有兴趣的朋友可以进一步思考或者搜索网上材料哈。
没有评论:
发表评论