# Fast python solution 160ms

• The algorithm is straightforward: use a map to record the value count and generate triplets with at least two identical elements. Then the list is de-duped and sorted so the normal two-pointer approach would apply. Running time is 160 ms.

``````class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
M = {}
for v in nums:
M[v] = M.get(v,0) + 1
results = []
for v in M.keys():
if v == 0:
if M[0] >= 3:
results.append([0,0,0])
else:
if M[v] >= 2 and -(v<<1) in M:
if v > 0:
results.append([-(v<<1),v,v])
else:
results.append([v,v,-(v<<1)])
nums = M.keys()
nums.sort()
N = len(nums)
for i in range(N-2):
start,end = i+1,N-1
while start < end:
if nums[start]+nums[end]+nums[i] < 0:
start += 1
elif nums[start]+nums[end]+nums[i] > 0:
end -= 1
else:
results.append([nums[i],nums[start],nums[end]])
start += 1
end -= 1
return results``````

• It's a little bit tedious, you have to take care of many details and you wouldn't have enough time to finish all these if it's real question in interview.

• Can you explain some of your optimizations? I am confused; why exclude starting and ending elements?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.