3Sum

15. 3Sum

Hash Table

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        num_dict = {}
        nums.sort()
        for x in nums:
            num_dict[x] = num_dict.get(x, 0) + 1
        for i in range(0, len(nums)):
            x = nums[i]
            if i > 0 and x == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums)):
                y = nums[j]
                if j - 1 != i and y == nums[j - 1]:
                    continue
                t = -(x + y)
                if t < y:
                    continue
                if num_dict.get(t, 0) == 0:
                    continue
                if num_dict.get(t, 0) >= 1 + (x == t) + (y == t):
                    ans.append([x, y, t])
        return ans

Tow Pointers

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums.sort()
        for i in range(0, n):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j = i + 1
            k = n - 1
            while j < k:
                if nums[j] + nums[k] > -nums[i]:
                    k -= 1
                elif nums[j] + nums[k] < -nums[i]:
                    j += 1
                else:
                    ans.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    while j < k and nums[k] == nums[k - 1]:
                        k -= 1
                    j += 1
                    k -= 1
        return ans

Reference:

1. Blind Curated 75
2. 花花酱 LeetCode 15. 3Sum - 刷题找工作 EP383

Comments