3Sum

[huimeich]

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

[huimeich]

def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    first = 0
    result = []
    nums_dict = {}
    for num in nums:
        nums_dict[num] = 0
    while (first < len(nums) - 2):
        second = first + 1
        while second < len(nums) - 1:
            tofind = 0 - nums[first] - nums[second]
            if tofind > nums[second] and tofind in nums_dict:
                result += [[nums[first], nums[second], tofind]]
            elif tofind == nums[second + 1]:
                result += [[nums[first], nums[second], tofind]]
            second += 1
            while (second < len(nums) - 1 and nums[second] == nums[second - 1]):
                second += 1
        first += 1
        while (first < len(nums)-2 and nums[first] == nums[first - 1]):
            first += 1
    return result

[huimeich]

def threeSum(self, n: List[int]) -> List[List[int]]:
    n.sort()
    result = set()
    ndict = {j:i for i, j in enumerate(n)}
    for first in range(0, len(n) - 2):
        for second in range(first+1, len(n) - 1):
            tofind = 0 - n[first] - n[second]
            if tofind in ndict:
                if ndict[tofind] > second:
                    result.add((n[first], n[second], tofind))
    return result

[huimeich]

def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    ans = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i - 1] == nums[i]:
            continue
        used = []
        sj = set()
        for j in range(i+1, len(nums)):
            if nums[j] in used:
                continue
            if -nums[i] - nums[j] in sj:
                ans.append([nums[i], -nums[i]-nums[j], nums[j]])
                used.append(nums[j])
            else:
                sj.add(nums[j])
    return ans