Leetcode 3Sum Solution

This code implements the "Three Sum" problem using a two-pointer approach. The problem requires finding all unique triplets in the array that sum up to zero.


class Solution(object):
    def threeSum(self, nums):
        l = len(nums)
        nums.sort()
        out = set()

        for i in range(l):
            bam = i+1
            dan = l-1

            while(bam<dan):
                total = nums[i]+nums[bam]+nums[dan]
                if total == 0:
                    out.add((nums[i],nums[bam],nums[dan]))
                if total<0:
                    bam+=1
                else:
                    dan-=1

        return out

Let's go through the code step by step:

  1. l = len(nums): This line calculates the length of the input list nums.

  2. nums.sort(): This line sorts the input list nums in non-decreasing order. Sorting the array allows us to use a two-pointer approach efficiently.

  3. out = set(): This line initializes an empty set called out. We are going to use a set to store unique triplets.

  4. The code then iterates through the array using a for loop:

    • for i in range(l):: It iterates over each element in the array.

  5. Inside the loop, it sets up two pointers bam and dan:

    • bam = i + 1: bam starts from the element after the current element i.
    • dan = l - 1: dan starts from the last element in the array.

  6. It uses a while loop to find triplets that sum up to zero:

    • while(bam < dan): This loop runs as long as the pointer bam is less than dan.

  7. It calculates the total sum of the current triplet:

    • total = nums[i] + nums[bam] + nums[dan]

  8. It checks the sum:

    • If total is equal to zero, which means we found a triplet that sums up to zero. It adds this triplet to the set out.
    • If total is less than zero, it means we need to increase the sum, so it increments bam.
    • If total is greater than zero, it means we need to decrease the sum, so it decreases dan.
  9. Once all the elements are processed, the function returns the set out containing unique triplets that sum up to zero.

This approach ensures that no duplicate triplets are added to the final output set, thanks to a set data structure. Additionally, sorting the array enables efficient traversal and ensures that identical triplets won't be repeated.