LeetCode 15三数の和3 Sum Python

ハッシュ表のLeetCodeについて問題のノートを作って、Pythonは実現します
15.三数の和3 Sum
LeetCodeCN第15題リンク
第一の方法:三重遍歴、時間複雑度O(n^3)第2の方法:2重の遍歴で最初の2つの数を取得し、3番目の数-(a+b)が存在するかどうかを問い合わせる.ハッシュ表set()で

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]) :
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-(v+x)] = 1
                else:
                    res.add((v, -(v+x), x))
        return map(list, res)

第3の方法:まず昇順に並べ替えて、何度も繰り返して、それから後ろの新しい配列の中で2つのポインタで3つの数の和が0であるかどうかを検査して、0より大きいと右のポインタは左へ行って、0より小さいと左のポインタは右へ行きます.

class Solution(object):
    def threeSum(self, nums):
        if len(nums) < 3:
            return []
        nums.sort()
        res = []
        for i, x in enumerate(nums[:-2]):
            if i >= 1 and x == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
        return res

下一題:1.2つの数の和Two Sum