# 3Sum - leetcode

Question:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Here's my pythonic approach to leetcode 3Sum, it passes and actually beats 93% in time! However, the code is unweildy and the approach seems much overly complicated. I am looking to clean up the two sum function, and overall approach, but I'm not sure how.

    def threeSum(self, nums: List[int]) -> List[List[int]]:
def twoSum(i,target):
ans = []
for j in range(i+1,len(nums)):
#avoid dupes
if j > i+1 and nums[j] == nums[j-1]:
continue
if nums[j] > target//2:
break
# when target is even, two dupes may add to make it
if nums[j] == target/2 and j+1 < len(nums):
if nums[j+1] == target // 2:
ans.append([nums[i],nums[j],nums[j+1]])
break
elif -(-target + nums[j]) in values and -(-target + nums[j]) != nums[j]:
ans.append([nums[i],nums[j],-(-target + nums[j])])
return ans

values = set(nums)
nums.sort()
for i,num in enumerate(nums):
if i > 0 and nums[i-1] == nums[i]:
continue
values.remove(num)



Even if you aren't able to follow my code, I would really appreciate general pythonic tips. Thanks!

• Providing the problem statement and/or sample in- and output will help contributors point you towards a better or more straightforward solution. As it is now, it's hard to understand what's (supposed to be) going on. – riskypenguin Apr 23 at 23:28
• It doesn't address Python-specific questions, but the Wikipedia pseudocode for 3sum is intuitive and has a nice visualization to accompany it. Seems like a simpler algorithmic approach than the one you've taken, so it might be worth a look. – FMc Apr 24 at 23:38

You can just create every possible triplets with nested loops and keep a record of those that satisfy the requirements.

I don't know Python, so I learned a bit of it to write this code, take it as an example and translate it to proper Python. I think that the main issue of the code is the usage of while loops. I am used to the C's for loops where you have direct access to the indexes of the elements, and here I used while loops as equivalent even thought I saw there are better ways in Python.

It's a pretty straightforward approach:

n = [-1,0,1,2,-1,-4]
l = len(n)
triplets = []

i = 0
while i < l - 2:
j = i + 1
while j < l - 1:
k = j + 1
while k < l:
if n[i] + n[j] + n[k] == 0:
candidate = [n[i], n[j], n[k]]
unique = True
for tri in triplets:
if set(candidate) == set(tri):
unique = False
break
if unique:
triplets.append(candidate)
k += 1
j += 1
i += 1

print(triplets)


You could improve the algorithm by skipping a lap of the first loop if n[i] is a dupe of a previous n[i].