Take notes about LeetCode of hash table and implement it in Python

15. Sum of three 3 sum

LeetCodeCN question 15 link

The first method: triple traversal, time complexity O(n^3)

The second method: Double traverse to get the first two numbers, and then query whether the third number - (a+b) exists. Use hash table 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)

The third method: first sort in ascending order and traverse it once, and then check whether the sum of three numbers is 0 with double pointers in the new array. If it is greater than 0, the right pointer will go to the left, and if it is less than 0, the left pointer will go to the right.

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

Two Sum