原題鏈接:? http://oj.leetcode.com/problems/4sum/ ?
這道題要求跟 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里面，這樣得到新結果如果是重復的就不加入結果集了。
代碼如下： 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的問題，基本思想就是和第二種方法一樣進行二分，然后兩兩結合，不過細節就非常復雜了（這點從上面的第二種解法就能看出來），所以不是很適合在面試中出現，有興趣的朋友可以進一步思考或者搜索網上材料哈。

總結

以上是生活随笔為你收集整理的4Sum -- LeetCode的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。