Leetcode 15. 3Sum

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Using two pointer techniques, we can simply go through all combinations.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sorted_nums = sorted(nums)

        result = set()

        first_index = 0 
        end_index = len(sorted_nums) - 1

        while first_index < (len(sorted_nums) - 2) and sorted_nums[first_index] <= 0:
            second_index = first_index + 1
            third_index = len(sorted_nums) - 1

            while second_index < third_index:
                total = sorted_nums[first_index] + sorted_nums[second_index] + sorted_nums[third_index]

                if total > 0:
                    third_index -= 1
                elif total < 0:
                    second_index += 1
                else:
                    result.add((sorted_nums[first_index], sorted_nums[second_index], sorted_nums[third_index]))
                    third_index -= 1
                    second_index += 1
                    
                    while second_index < third_index and sorted_nums[second_index - 1] == sorted_nums[second_index]:
                        second_index += 1

                    while second_index < third_index and sorted_nums[third_index + 1] == sorted_nums[third_index]:
                        third_index -= 1

            first_index += 1

        return result