I use a dummy solution to solve the leetcode 3Sum problem.
I employ the set data type to handle duplicates, then transform back to list.
Given an array
nums
of n integers, are there elements a, b, c innums
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] ]
My codes:
from typing import List
import logging
import unittest
import random
from collections import defaultdict,Counter
##logging.disable(level=#logging.CRITICAL)
##logging.basicConfig(level=#logging.DEBUG, format="%(levelname)s %(message)s")
class Solution:
def threeSum(self, nums, target: int=0) -> List[List[int]]:
"""
:type nums: List[int]
:type target: int
"""
if len(nums) < 3: return []
triplets = []
if target == [0, 0, 0]:
triplets.append([0, 0, 0])
return triplets # finish fast
lookup = {nums[i]:i for i in range(len(nums))} #overwrite from the high
if len(lookup) == 1:#assert one identical element
keys = [k for k in lookup.keys()]
if keys[0] != 0:
return []
else:
triplets.append([0,0,0])
return triplets
triplets_set = set()
for i in range(len(nums)):
num_1 = nums[i]
sub_target = target - num_1
# #logging.debug(f"level_1_lookup: {lookup}")
for j in range(i+1, len(nums)):
num_2 = nums[j]
num_3 = sub_target - num_2
k = lookup.get(num_3) #
if k not in {None, i, j}: #don't reproduce itself
result = [num_1, num_2, num_3]
result.sort()
result = tuple(result)
triplets_set.add(result)
triplets = [list(t) for t in triplets_set]
return triplets
My solution gets this result:
Your runtime beats 28.86 % of python3 submissions.
Could anyone please give hints to improve?
target: int
== [0, 0, 0]
? \$\endgroup\$ – greybeard Mar 26 '19 at 6:31hints to improve
instead of a turn-key solution, on (seemingly) trying to come up with a solution of your own instead of scraping the web/SE/leetcode. Way to learn! \$\endgroup\$ – greybeard Mar 28 '19 at 6:04