https://leetcode.com/problems/3sum/

个人解答

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         nums.sort()
  4.         res = []
  5.         for i in range(len(nums)):
  6.             # skip duplicate
  7.             if i > 0 and nums[i] == nums[i - 1]:
  8.                 continue
  10.             j, k = i + 1, len(nums) - 1
  11.             while j < k:
  12.                 if nums[i] + nums[j] + nums[k] == 0:
  13.                     res.append([nums[i], nums[j], nums[k]])
  14.                     j += 1
  15.                     while j < len(nums) and nums[j] == nums[j - 1]:
  16.                         j += 1
  17.                     k -= 1
  18.                     while k >= 0 and nums[k] == nums[k + 1]:
  19.                         k -= 1
  20.                 elif nums[i] + nums[j] + nums[k] > 0:
  21.                     k -= 1
  22.                 else:
  23.                     j += 1
  24.         return res

题目分析

太过经典，没什么好说的。
唯一需要说明的是，关于重复的处理，可以预先处理然后分情况讨论（1，2，3），（1，1， 2），（1，2，2），（1，1，1）的情况：

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         c = collections.Counter(nums)
  4.         n = sorted(c.keys())
  5.         res = []
  6.         for i, a in enumerate(n):
  7.             if c[a] >= 3 and 3 * a == 0:
  8.                 res.append([a] * 3)
  9.             if c[a] >= 2 and -2 * a in c and -2 * a > a:
  10.                 res.append([a, a, -2 * a])
  11.             if -a % 2 == 0 and c[-a // 2] >= 2 and -a // 2 > a:
  12.                 res.append([a, -a // 2, -a // 2])
  14.             j, k = i + 1, len(n) - 1
  15.             while j < k:
  16.                 v = n[j] + n[k]
  17.                 if v == -a:
  18.                     res.append([a, n[j], n[k]])
  19.                     k -= 1
  20.                     j += 1
  21.                 elif v > -a:
  22.                     k -= 1
  23.                 else:
  24.                     j += 1
  25.         return res

也可以像个人解答里边那样，在遍历的时候跳过重复的。
两种方法都要考虑一些特殊情况。