LC15 3Sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # main idea: sort + two pointers
        # time O(N^2) space O(1)
        nums.sort()
        res = []
        size = len(nums)
        for i in range(size-2):
        # optimization:  since nums is sorted, it is impossible to have a sum of 0
            if nums[i] > 0 :
                break
             # from i+1, to prevent duplicate number
            lo, hi = i+1, size-1
            if i> 0 and nums[i] == nums[i-1]:
                continue
            
            while lo < hi:
                sum = nums[i] + nums[lo] + nums[hi]
                if sum < 0:
                    lo += 1
                elif sum > 0:
                    hi -= 1
                else:
                    res.append([nums[i],nums[lo],nums[hi]])
                    # skip duplicates while prevent out of bound error
                    while lo < hi and nums[lo] == nums[lo + 1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi - 1]:
                        hi -= 1
                    lo += 1
                    hi -= 1
        return res