[leetcode]4Sum @ Python

原題住所:http://oj.leetcode.com/problems/4sum/
題意:配列から4つの数を見つけて、それらの和をtargetにします.重いことを要求して、多くのグループの解があるかもしれませんが、すべて探し出す必要があります.
解題構想:最初は3 Sumのように解題したいと思っていましたが、時間の複雑さはO(N^3)でしたが、どう書いてもTime Limited Exceededです.同じアルゴリズムはC++を用いて通過できる.Pythonの実行速度はC++よりずっと遅いことを示しています.もう一つ説明しましたが、出題者の意味は3 Sumのように問題を解くことではありません.そうしないと、この問題は意味がありません.ここではkittの解法を参考にしました.http://chaoren.is-programmer.com/posts/45308.html
　　　　   ハッシュテーブルの構想を用いる必要があり、これにより、空間的に時間を交換し、空間的複雑度の代価を増加させて時間的複雑度を低減することができる.まず、辞書dictを作成します.辞書のkey値は配列内の2つの要素の和であり、各keyに対応するvalueはこの2つの要素の下付き記号からなるメタグループであり、メタグループは必ずしも一意ではありません.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]

渡れないO(N^3)の書き方をもう2つ貼ります.
1:

class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        num.sort(); res=[]
        for i in range(len(num)):
            if i>0 and num[i]==num[i-1]: continue
            for j in range(i+1,len(num)):
                if j>i+1 and num[j]==num[j-1]: continue
                l=j+1; r=len(num)-1
                while l<r:
                    sum=num[i]+num[j]+num[l]+num[r]
                    if sum>target:
                        r-=1
                    elif sum<target:
                        l+=1
                    elif l>j+1 and num[l]==num[l-1]:
                        l+=1
                    elif r<len(num)-1 and num[r]==num[r+1]:
                        r-=1
                    else:
                        res.append([num[i],num[j],num[l],num[r]])
                        l+=1; r-=1
        return res

2:

class Solution:
    # @return a list of lists of length 4, [[val1,val2,val3,val4]]
    def fourSum(self, num, target):
        num.sort(); res=[]
        for i in range(len(num)-3):
            if i==0 or num[i]>num[i-1]:
                for j in range(i+1,len(num)-2):
                    if j==i+1 or num[j]>num[j-1]:
                        left=j+1; right=len(num)-1
                        while left<right:
                            if num[i]+num[j]+num[left]+num[right]==target:
                                res.append([num[i],num[j],num[left],num[right]])
                                left+=1; right-=1
                                while left<right and num[left]==num[left-1]: left+=1
                                while left<right and num[right]==num[right+1]: right-=1
                            elif num[i]+num[j]+num[left]+num[right]>target:
                                while left<right:
                                    right-=1
                                    if num[right]<num[right+1]: break
                            else:
                                while left<right:
                                    left+=1
                                    if num[left]>num[left-1]: break
        return res