Leetcode 18. 4Sum

https://leetcode.com/problems/4sum/

We have 2 sum, 3 sum, now 4 sum. Actually we can borrow idea from 3 sum: first we get all possible sums of two numbers, and then do it just like 3 sum. Note that arrange the sequence of 4 numbers to avoid repeat usage of the exactly same number.

Solution:

# T:O(n^2*t) S:O(n^2*t)
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 i in xrange(numLen):
            for j in xrange(i+1, numLen): 
                if num[i]+num[j] not in dict:
                    dict[num[i]+num[j]] = [(i,j)]
                else:
                    dict[num[i]+num[j]].append((i,j))
        for i in xrange(numLen):
            for j in xrange(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]

Run Time: 236 ms