Jianbo Dai's

mq013.三数之和

 
  • Dec 04, 2020

题目链接

这题可以用双指针法解决，与两数之和这题类似。难点在于题目要求返回的数组中不含有重复的数对。实现如下，其中带注释的行是有在做跳过重复字符这件事。这个算法的时间复杂度是O（N^2），空间复杂度是O（1）。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(len(nums)-2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]: # skip the same first number
                continue
            p_left, p_right = i + 1, len(nums)-1
            while p_left < p_right:
                if nums[p_left] + nums[p_right] > -nums[i]:
                    p_right -= 1
                elif nums[p_left] + nums[p_right] < -nums[i]:
                    p_left += 1
                else:
                    ans.append([nums[i], nums[p_left], nums[p_right]])
                    while p_left < p_right and nums[p_left] == nums[p_left+1]: # skip the same second number
                        p_left += 1
                    while p_left < p_right and nums[p_right] == nums[p_right-1]: # skip the same third number
                        p_right -= 1
                    p_left += 1
                    p_right -= 1
        return ans
Search