18. 4Sum

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)

跟之前的 2Sum, 3Sum 和 3Sum Closest 一样的做法，先排序，再左右夹逼，复杂度 O(n^3)
先求出每两个数的和，放到 HashSet 里，再利用之前的 2Sum 去求。这种算法比较快，复杂度 O(nnlog(n))，不过细节要处理的不少。

public class Solution {  
    public List<List<Integer>> fourSum(int[] num, int target) {  
        List<List<Integer>> ret = new ArrayList<List<Integer>>();  
        HashMap<Integer, List<Integer[]>> hm = new HashMap<Integer, List<Integer[]>>();  
        int len = num.length;  
  
        Arrays.sort(num);  
        // store pair  
        for (int i = 0; i < len - 1; ++i) {  
            for (int j = i + 1; j < len; ++j) {  
                int sum = num[i] + num[j];  
                Integer[] tuple = {num[i], i, num[j], j};  
                if (!hm.containsKey(sum)) {  
                    hm.put(sum, new ArrayList<Integer[]>());  
                }  
                hm.get(sum).add(tuple);  
            }  
        }  
  
        Integer[] keys = hm.keySet().toArray(new Integer[hm.size()]);  
        for (int key : keys) {  
            if (hm.containsKey(key)) {  
                if (hm.containsKey(target - key)) {  
                    List<Integer[]> first_pairs = hm.get(key);  
                    List<Integer[]> second_pairs = hm.get(target - key);  
  
                    for (int i = 0; i < first_pairs.size(); ++i) {  
                        Integer[] first = first_pairs.get(i);  
                        for (int j = 0; j < second_pairs.size(); ++j) {  
                            Integer[] second = second_pairs.get(j);  
                            // check  
                            if (first[1] != second[1] && first[1] != second[3] &&  
                                    first[3] != second[1] && first[3] != second[3]) {  
                                List<Integer> ans = Arrays.asList(first[0], first[2], second[0], second[2]);  
                                Collections.sort(ans);  
                                if (!ret.contains(ans)) {  
                                    ret.add(ans);  
                                }  
                            }  
                        }  
                    }  
  
                    hm.remove(key);  
                    hm.remove(target - key);  
                }  
            }  
        }  
  
        return ret;  
    }  
}

解题思路：一开始想要像3Sum那样去解题，时间复杂度为O(N^3)，可无论怎么写都是Time Limited Exceeded。而同样的算法使用C++是可以通过的。说明Python的执行速度比C++慢很多。还说明了一点，大概出题人的意思不是要让我们去像3Sum那样去解题，否则这道题就出的没有意义了。这里参考了kitt的解法：http://chaoren.is-programmer.com/posts/45308.html

　　　　需要用到哈希表的思路，这样可以空间换时间，以增加空间复杂度的代价来降低时间复杂度。首先建立一个字典dict，字典的key值为数组中每两个元素的和，每个key对应的value为这两个元素的下标组成的元组，元组不一定是唯一的。如对于num=[1,2,3,2]来说，dict={3:[(0,1),(0,3)], 4:[(0,2),(1,3)], 5:[(1,2),(2,3)]}。这样就可以检查target-key这个值在不在dict的key值中，如果target-key在dict中并且下标符合要求，那么就找到了这样的一组解。由于需要去重，这里选用set()类型的数据结构，即无序无重复元素集。最后将每个找出来的解(set()类型)转换成list类型输出即可。

class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        numLen, res, dict = len(num), set(), {}
        if numLen < 4: return []
        num.sort()
        for p in range(numLen):
            for q in range(p+1, numLen): 
                if num[p]+num[q] not in dict:
                    dict[num[p]+num[q]] = [(p,q)]
                else:
                    dict[num[p]+num[q]].append((p,q))
        for i in range(numLen):
            for j in range(i+1, numLen-2):
                T = target-num[i]-num[j]
                if T in dict:
                    for k in dict[T]:
                        if k[0] > j: res.add((num[i],num[j],num[k[0]],num[k[1]]))
        return [list(i) for i in res]