题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

  1. [
  2.   [-1, 0, 1],
  3.   [-1, -1, 2]
  4. ]

方案一

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         # 双指针
  4.         if len(nums) < 2:
  5.             return []
  7.         nums.sort()
  8.         i, j, k = 1, len(nums) - 1, 0
  9.         res = []
  10.         # 固定一个指针 k
  11.         while k < len(nums):
  12.             if nums[k] > 0:  # 最小的数大于 0
  13.                 break
  14.             # i, j 从两端往中间步进
  15.             while i < j:
  16.                 count = nums[k] + nums[i] + nums[j]
  17.                 if count == 0:
  18.                     res.append([nums[k], nums[i], nums[j]])
  19.                     i += 1
  20.                     j -= 1
  21.                     while i < j:
  22.                         if nums[i] == nums[i - 1]:  # 连续相同
  23.                             i += 1
  24.                         else:
  25.                             break
  26.                     while i < j:
  27.                         if nums[j] == nums[j + 1]:  # 连续相同
  28.                             j -= 1
  29.                         else:
  30.                             break
  31.                 elif count < 0:
  32.                     i += 1
  33.                     while i < j:
  34.                         if nums[i] == nums[i - 1]:  # 连续相同
  35.                             i += 1
  36.                         else:
  37.                             break
  38.                 else:
  39.                     j -= 1
  40.                     while i < j:
  41.                         if nums[j] == nums[j + 1]:  # 连续相同
  42.                             j -= 1
  43.                         else:
  44.                             break
  46.             k += 1
  47.             while k < len(nums):
  48.                 if nums[k] == nums[k - 1]:  # 连续相同
  49.                     k += 1
  50.                 else:
  51.                     break
  52.             i = k + 1
  53.             j = len(nums) - 1
  54.         return res

优化代码结构

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         # 双指针
  4.         if len(nums) < 2:
  5.             return []
  7.         nums.sort()
  8.         i, j, k = 1, len(nums) - 1, 0
  9.         res = []
  10.         # 固定一个指针 k
  11.         while k < len(nums):
  12.             if nums[k] > 0:  # 最小的数大于 0
  13.                 break
  14.             while i < j:
  15.                 count = nums[k] + nums[i] + nums[j]
  16.                 if count == 0:
  17.                     res.append([nums[k], nums[i], nums[j]])
  18.                     i += 1
  19.                     j -= 1
  20.                     # 跳过相同元素
  21.                     while i < j and nums[i] == nums[i - 1]: i += 1
  22.                     while i < j and nums[j] == nums[j + 1]: j -= 1
  23.                 elif count < 0:
  24.                     i += 1
  25.                     while i < j and nums[i] == nums[i - 1]: i += 1
  26.                 else:
  27.                     j -= 1
  28.                     while i < j and nums[j] == nums[j + 1]: j -= 1
  30.             k += 1
  31.             while k < len(nums) - 1 and nums[k] == nums[k - 1]: k += 1
  32.             # 重置 i, j 指针
  33.             i = k + 1
  34.             j = len(nums) - 1
  35.         return res
  1. class Solution:
  3.     def twoSum(self, nums, target, l, r):
  4.         """
  5.         :type nums: List[int]
  6.         :type target: int
  7.         :rtype: List[int]
  8.         """
  10.         n = len(nums[l: r+1])
  11.         if n < 2:
  12.             return set()
  14.         start = nums[l - 1]
  15.         dict1 = dict()
  16.         ret = set()
  17.         for i in range(l, r+1):
  18.             other = target - nums[i]
  19.             if other in dict1:
  20.                 ret.add((start, other, nums[i]))
  21.             dict1[nums[i]] = i
  23.         return ret
  25.     def threeSum(self, nums):
  26.         """
  27.         :type nums: List[int]
  28.         :type target: int
  29.         :rtype: List[int]
  30.         """
  32.         n = len(nums)
  33.         if n < 3:
  34.             return []
  36.         nums.sort()
  38.         ret = set()
  39.         for i in range(n):
  40.             # nums[i] 为正数，表示后面不可能有两数之后为负
  41.             if nums[i] > 0:
  42.                 break
  43.             if (i >= 1 and nums[i] == nums[i-1]):
  44.                 continue
  45.             ll = self.twoSum(nums, -nums[i], i+1, n-1)
  46.             if ll == set():
  47.                 continue
  48.             ret = ret | ll
  49.         return list(ret)