4Sum：LeetCode

4Sum：LeetCode2015-09-26这道题要求跟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）是有提高的。