首页 > 代码库 > Leetcode: 4Sum

Leetcode: 4Sum

2024-07-26 17:32:24   212人阅读

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.Note:Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)The solution set must not contain duplicate quadruplets.    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.    A solution set is:    (-1,  0, 0, 1)    (-2, -1, 1, 2)    (-2,  0, 0, 2)

可以按照3Sum的思路来做，并以此类推，KSum的复杂度就是O(N^(k-1)). 在3Sum外面再套一层循环，相当于N次求3Sum

 1 public class Solution { 2     public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { 3         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 4         if (num==null || num.length==0) return res; 5         Arrays.sort(num); 6         for (int i=num.length-1; i>=3; i--) { 7             if (i<num.length-1 && num[i]==num[i+1]) continue; 8             ArrayList<ArrayList<Integer>> sets = threeSum(0, i-1, num, target-num[i]); 9             for (int ii=0; ii<sets.size(); ii++) {10                 ArrayList<Integer> temp = sets.get(ii);11                 temp.add(num[i]);12             }13             res.addAll(sets);14         }15         return res;16     }17     18     public ArrayList<ArrayList<Integer>> threeSum(int start, int end, int[] num, int target) {19         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();20         for (int j=end; j>=2; j--) {21             if (j<end && num[j]==num[j+1]) continue;22             ArrayList<ArrayList<Integer>> sets = twoSum(0, j-1, num, target-num[j]);23             for (int jj=0; jj<sets.size(); jj++) {24                 ArrayList<Integer> temp = sets.get(jj);25                 temp.add(num[j]);26             }27             res.addAll(sets);28         }29         return res;30     }31     32     public ArrayList<ArrayList<Integer>> twoSum(int l, int r, int[] num, int target) {33         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();34         while (l < r) {35             if (num[l]+num[r] == target) {36                 ArrayList<Integer> set = new ArrayList<Integer>();37                 set.add(num[l]);38                 set.add(num[r]);39                 res.add(new ArrayList<Integer>(set));40                 l++;41                 r--;42                 while (l<r && num[l] == num[l-1]) {43                     l++;44                 }45                 while (l<r && num[r] == num[r+1]) {46                     r--;47                 }48             }49             else if (num[l]+num[r] < target) {50                 l++;51             }52             else {53                 r--;54             }55         }56         return res;57     }58 }

（未深究）网上还看到一种方法，就是如果想那么时间复杂度更好的话，其实我们可以考虑用二分法的思路，如果把所有的两两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里面，这样得到新结果如果是重复的就不加入结果集了。

 1 private ArrayList<ArrayList<Integer>> twoSum(ArrayList<Pair> pairs, int target){ 2     HashSet<Tuple> hashSet = new HashSet<Tuple>(); 3     int l = 0; 4     int r = pairs.size()-1; 5     ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 6     while(l<r){ 7         if(pairs.get(l).getSum()+pairs.get(r).getSum()==target) 8         { 9             int lEnd = l;10             int rEnd = r;11             while(lEnd<rEnd && pairs.get(lEnd).getSum()==pairs.get(lEnd+1).getSum())12             {13                 lEnd++;14             }15             while(lEnd<rEnd && pairs.get(rEnd).getSum()==pairs.get(rEnd-1).getSum())16             {17                 rEnd--;18             }19             for(int i=l;i<=lEnd;i++)20             {21                 for(int j=r;j>=rEnd;j--)22                 {23                     if(check(pairs.get(i),pairs.get(j)))24                     {25                         ArrayList<Integer> item = new ArrayList<Integer>();26                         item.add(pairs.get(i).nodes[0].value);27                         item.add(pairs.get(i).nodes[1].value);28                         item.add(pairs.get(j).nodes[0].value);29                         item.add(pairs.get(j).nodes[1].value);30                         //Collections.sort(item);31                         Tuple tuple = new Tuple(item);32                         if(!hashSet.contains(tuple))33                         {34                             hashSet.add(tuple);35                             res.add(tuple.num);36                         }37                     }                        38                 }39             }40             l = lEnd+1;41             r = rEnd-1;42         }43         else if(pairs.get(l).getSum()+pairs.get(r).getSum()>target)44         {45             r--;46         }47         else{48             l++;49         }50     }51     return res;52 }53 private boolean check(Pair p1, Pair p2)54 {55     if(p1.nodes[0].index == p2.nodes[0].index || p1.nodes[0].index == p2.nodes[1].index)56         return false;57     if(p1.nodes[1].index == p2.nodes[0].index || p1.nodes[1].index == p2.nodes[1].index)58         return false;59     return true;60 }

 

Leetcode: 4Sum


联系
我们