"""
sort and two pointers (twosum2)
"""

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i+1
            right = len(nums)-1
            
            while left < right:
                cur_sum = nums[i] + nums[left] + nums[right]

                if cur_sum > 0:
                    right -=1
                elif cur_sum < 0:
                    left +=1
                else:
                    result.append([nums[i],nums[left],nums[right]])
                    left +=1
                    while nums[left] == nums[left-1] and left < right:
                        left +=1
                    
                    
        return result 