华为 OD 训练营 · 题解精讲

LC15. 三数之和

题目描述

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

题目解析

解题思路

本题要求在数组中找出所有和为 0 且不重复的三元组。核心思路是排序 + 双指针。首先将数组排序，然后固定一个元素 nums[i]，再用两个指针 left 和 right 分别指向 i+1 和数组末尾，通过移动双指针来寻找满足 nums[i] + nums[left] + nums[right] == 0 的组合。排序的目的是让双指针可以根据当前和的大小单向移动，从而将时间复杂度从 O(n³) 降至 O(n²)。

关键步骤

1. 排序：对 nums 升序排序，为后续双指针操作和去重创造条件。 2. 外层循环：遍历 i 从 0 到 len(nums)-1：

若 nums[i] > 0，由于排序后后面元素更大，三数之和必大于 0，直接 break。
去重：若 i > 0 且 nums[i] == nums[i-1]，跳过当前 i，避免重复三元组。

3. 双指针内循环：初始化 left = i+1，right = len(nums)-1：

计算 sum = nums[i] + nums[left] + nums[right]。
若 sum == 0：记录结果，然后对 left 和 right 进行去重（跳过相同值），最后 left++、right--。
若 sum < 0：left++ 增大和。
若 sum > 0：right-- 减小和。

去重示意图（以 [-2,0,0,2,2] 为例）：


i=0 (-2)  left=1 (0)  right=4 (2)  → sum=0，记录[-2,0,2]
          left=2 (0)  right=3 (2)  → 若不跳过，又会记录相同三元组
          通过 while 循环跳过重复的 left 和 right

复杂度分析

时间复杂度：O(n²)。排序 O(n log n)，外层循环 O(n)，内层双指针 O(n)，总体 O(n²)。
空间复杂度：O(log n) 或 O(n)，取决于排序算法的实现（Python 的 sort() 为 O(n) 额外空间）。结果数组不计入空间复杂度。

参考代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 三数之和(15)：https://leetcode-cn.com/problems/3sum/ 
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 题目存在多组解，每一组解都是一个数组，所以使用二维数组存储所有的解
        ans = []


        # 边界情况判断
        if nums == None or len(nums) < 3 :
           return ans

        # 先将数组进行排序操作，从小到大
        nums.sort()

        # 开始遍历整个数组
        # 在遍历的过程中，观察设置的三个位置的元素之后的大小
        # num[i] 为从左到右观察过去的元素
        # left 为从 i 到 len - 1 的元素
        # right 为从 len - 1 向左移动到 i 的元素
        for i in range(len(nums)) :

            # 如果发现 nums[i] > 0 ，由于 nums 是递增序列，left 在 nums[i] 的右侧，right 也在 nums[i] 的右侧
            # 那么 num[i]、nums[left]、nums[right] 都大于 0 
            # 说明这三数之和一定大于 0 ，结束循环
            if nums[i] > 0 : 
                break 

            # 答案中不可以包含重复的三元组，所以需要执行一个去重的操作
            # 比如这个输入 [-4,-1,-1,0,1,2]
            # i 指向的为第一个 -1 时，left 指向的元素值为 0 ，right 指向的元素值为 1 
            # i 指向的为第二个 -1 时，left 指向的元素值为 0 ，right 指向的元素值为 1 
            # 这两组解都是 [ -1 , 0 , 1]，所以需要去重
            if i > 0 and nums[i] == nums[ i - 1 ] :
               continue 

            # left 为从 i 到 len - 1 的元素，向右移动
            left = i + 1

            # right 为从 len - 1 向左移动到 i 的元素，向左移动
            right = len(nums) - 1

            # left 和 right 不断的向内移动
            while left < right :
                
                # 计算这三者之和
                sum = nums[i] + nums[left] + nums[right]
                
                # 发现三者之和为 0
                if sum == 0 :

                    # 把这个结果记录一下
                    ans.append([nums[i],nums[left],nums[right]])
            

                    # 答案中不可以包含重复的三元组，所以需要执行一个去重的操作
                    # 比如这个输入 [-2,0,0,2,2]
                    # i 指向的元素值为 -2 ，left 指向的元素值为第一个 0 ，right 指向的元素值为倒数第一个 2 时
                    # 它们的 sum 为 0 ，如果让 ，left 向右移动一下，，right 向左移动一下，它们的 sum 也为 0
                    # 但是这两组解都是 [ -2 , 0 , 2]，所以需要去重
                    while left < right and nums[left] == nums[ left + 1 ] :
                        # left 向右移动
                        left += 1
                    

                    while left < right and nums[right] == nums[ right - 1] :
                        # right 向左移动
                        right -= 1
                    

                    # left 向右移动
                    left += 1

                    # right 向左移动
                    right -= 1

                # 如果三者之和小于 0 ，那么说明需要找更大的数
                elif sum < 0 : 
                    # left 向右移动
                    left += 1

                # 如果三者之和大于 0 ，那么说明需要找更小的数
                elif sum > 0 : 
                    # right 向左移动
                     right -= 1
       
        # 返回结果   
        return ans
四、复杂度分析
时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。
空间复杂度：O(logN)。

← 上一篇

LC11. 盛水最多的容器

LC20. 有效的括号