LeetCode第15題-三数の和

1.テーマ
2.テーマの分析と構想
3.考え方
 
1.テーマ
n個の整数を含む配列numsを与え,numsにa,b,cの3つの要素が存在するか否かを判断し,a+b+c=0とする.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
例えば、所与の配列nums=[−1,0,1,2,−1,−4],
要求を満たす三元群の集合は,[−1,0,1],[−1,−1,2]]である.
2.考え方
この問題で最も直接思いついたのは2数の和で、2数の和はやはり比較的基礎的で、通知記録の方式を採用して、1つの辞書を維持して、新しい数がこの辞書の鍵に属するかどうかを見ることができます.三数の和も似たような方法を使うことができますが、テーマが要求しているのは繰り返してはいけません.これは難しいです.それはまずそれを並べ替えてから、彼らが集合中かどうかを判断するだけで、考えが明らかになります.コードは以下の通りです.

def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        for i,j in enumerate(nums):
            temp = nums[:i]+nums[i+1:]
            dic1 = {}
            dic2 = {}
            for count,k in enumerate(temp):
                if k not in dic1:
                    dic1[-j-k] = k
                else:
                    dic2[tuple(sorted([j,k,-j-k]))] = [j,k,-j-k]
        return dic2.values()

3.改善
しかし残念なことに、この複雑さは高すぎて、すべてのcaseを走ることができなくてタイムアウトして、その前に私が使ったのはlistがlistの中にあるかどうかを判断することで、このようにすると更にすべてのcaseを通じて、複雑さは高すぎて、最適化してから辞書を使うのですが、まだ0だらけのcaseで失敗しました.
修正後といくつかの境界条件を経て、caseを通過したが、極めて遅い解法を与え、私はそれを非情解法と呼んでいる.

def threeSum(self, nums: List[int]) -> List[List[int]]:
        dic2 = {}
        if (len(set(nums) ) == 1)and (len(nums) > 2): #       0    ，  0               
            if 0 in set(nums):
                return [[0,0,0]]
        for i,j in enumerate(nums):
            temp = nums[:i]+nums[i+1:]
            dic1 = {}
            for count,k in enumerate(temp):
                if k not in dic1:
                    dic1[-j-k] = k
                else:
                    dic2[tuple(sorted([j,k,-j-k]))] = [j,k,-j-k]
        return dic2.values()

次に正しい解法を示し,二重ポインタを用いる
 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        res = []
        dic1 = {}
        for i,j in enumerate(nums):
            if j > 0:
                continue
            temp = nums[i+1:]
            left = 0
            right = len(temp)-1
            while(left < right):
                
                if j + temp[left]+temp[right] == 0:
                    dic1[(j,temp[left],temp[right])] = [j,temp[left],temp[right]]
                    # res.append([j,temp[left],temp[right]])
                    right -= 1
                elif j + temp[left]+temp[right] > 0:
                    right -= 1
                else:
                    left += 1
        return dic1.values()