15. 三数之和#

题目链接: LeetCode 15

题目描述#

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

答案中不可以包含重复的三元组。

示例 1：

1
输入：nums = [-1,0,1,2,-1,-4]
2
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

1
输入：nums = [0,1,1]
2
输出：[]

示例 3：

1
输入：nums = [0,0,0]
2
输出：[[0,0,0]]

解题思路#

核心思想#

先排序，固定第一个数 nums[i]，再用双指针在 [i+1, n-1] 内找两数之和等于 -nums[i]。排序让双指针可以有序移动，也让去重变得简单：跳过重复的元素避免产生重复三元组。

算法步骤#

排序 nums。
遍历 i（0 到 n-3）：
- 若 i > 0 且 nums[i] == nums[i-1]，跳过（去重）。
- left=i+1, right=n-1, target=-nums[i]。
- 双指针寻找两数之和等于 target：
  - 相等：加入答案，并移动 left/right 跳过重复值。
  - 小于 target：left += 1。
  - 大于 target：right -= 1。
返回答案。

逐步举例#

nums = [-1,0,1,2,-1,-4]，排序后 [-4,-1,-1,0,1,2]：

i=0，nums[0]=-4，target=4。双指针 [-1,2]→1, [0,2]→2, [1,2]→3 都 < 4，找不到。
i=1，nums[1]=-1，target=1。left=2,right=5：[-1,2]→1 == target ✅ 得 [-1,-1,2]；[0,2]→2 > 1 → right=3；[0,1]→1 == target ✅ 得 [-1,0,1]。
i=2，nums[2]=-1 == nums[1] 跳过。

答案 [[-1,-1,2],[-1,0,1]]。

复杂度分析#

时间复杂度：O(n²)，排序 O(n log n)，双指针双层循环。
空间复杂度：O(1)（不计排序栈空间，排序通常 O(log n)）。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def threeSum(self, nums: List[int]) -> List[List[int]]:
6
        nums.sort()
7
        n = len(nums)
8
        ans = []
9
        for i in range(n - 2):
10
            if i > 0 and nums[i] == nums[i - 1]:
11
                continue
12
            left, right = i + 1, n - 1
13
            target = -nums[i]
14
            while left < right:
15
                s = nums[left] + nums[right]
16
                if s == target:
17
                    ans.append([nums[i], nums[left], nums[right]])
18
                    while left < right and nums[left] == nums[left + 1]:
19
                        left += 1
20
                    while left < right and nums[right] == nums[right - 1]:
21
                        right -= 1
22
                    left += 1
23
                    right -= 1
24
                elif s < target:
25
                    left += 1
26
                else:
27
                    right -= 1
28
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_basic(self):
12
        res = Solution().threeSum([-1, 0, 1, 2, -1, -4])
13
        expected = [[-1, -1, 2], [-1, 0, 1]]
14
        self.assertEqual(sorted(res), sorted(expected))
15

16
    def test_no_solution(self):
17
        self.assertEqual(Solution().threeSum([0, 1, 1]), [])
18

19
    def test_zeros(self):
20
        self.assertEqual(Solution().threeSum([0, 0, 0, 0]), [[0, 0, 0]])
21

22

23
if __name__ == '__main__':
24
    unittest.main()