2
\$\begingroup\$

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
                #traditional two sum variation
                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()
        answer = []
        for i,num in enumerate(nums):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            values.remove(num)
            answer.extend(twoSum(i,-num))

        return answer

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

\$\endgroup\$
2
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – riskypenguin Apr 23 at 23:28
  • \$\begingroup\$ 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. \$\endgroup\$ – FMc Apr 24 at 23:38
-1
\$\begingroup\$

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].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.