20211108-03 Three Sum

https://leetcode-cn.com/problems/3sum/submissions/

通过 sort 之后数组有序的特性，固定n-2个数，剩下的2个数利用 left, right 双指针进行查找

python

class Solution(object):
    def threeSum(self, nums):
        if len(nums) < 3:
            return []

        res = []
        nums.sort()
        for idx, num in enumerate(nums):
            if idx > 0 and nums[idx - 1] == nums[idx]:
                continue

            # 在 left 和 right 区间里查找是否有和为 -num 的两个数
            left, right = idx + 1, len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == (0 - num):
                    res.append( [num, nums[left], nums[right]] )
                    left += 1
                    right -= 1
                    # 小心越界，注意 left < right
                    while nums[left] == nums[left - 1] and left < right:
                        left += 1
                    while nums[right] == nums[right + 1] and left < right:
                        right -= 1
                elif nums[left] + nums[right] < (0 - num):
                    left += 1
                else:
                    right -= 1
            
        return res