When I was solving the leetcode 3sum problem, I submitted the following code:
class Solution1:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
res = set()
nums.sort()
for firstEle in range(len(nums)-2):
if firstEle > 0 and nums[firstEle] == nums[firstEle - 1]:
continue
target = 0 - nums[firstEle]
dic = {}
for j in range(firstEle+ 1,len(nums)):
if target - nums[j] in dic:
res.add((nums[firstEle], target - nums[j], nums[j]))
else:
dic[nums[j]] = j
return list(map(list, res))
and got an runtime of ~844 ms.
I replaced dict with set, and modified the code as follows:
class Solution2:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
res = set()
nums.sort()
for firstEle in range(len(nums)-2):
if firstEle > 0 and nums[firstEle] == nums[firstEle - 1]:
continue
target = 0 - nums[firstEle]
mem = set()
for j in range(firstEle+ 1,len(nums)):
if target - nums[j] in mem:
res.add((nums[firstEle], target - nums[j], nums[j]))
else:
mem.add(nums[j])
return list(map(list, res))
then got a runtime of ~1044 ms.
Why did the data structure set downgrade the efficiency?
Updated:
I tested the code on my laptop:
import timeit
s1 = Solution1()
s2 = Solution2()
print("dict:", timeit.timeit(lambda: s1.threeSum([-1, 0, 1, 2, -1, -4]), number=100000))
print("set:", timeit.timeit(lambda: s2.threeSum([-1, 0, 1, 2, -1, -4]), number=100000))
and got the output:
dict: 0.671448961016722
set: 0.7314219229156151
Environment:
MacBook Pro (Retina, 13-inch, Early 2015)
CPU: 2.7 GHz Intel Core i5
RAM: 8 GB 1867 MHz DDR3
Python version: 3.6
It seems set is still slower.
