优化LeetCode三数之和问题：从超时到高效的两指针解法

---

本文深入探讨leetcode三数之和问题，分析常见超时解法的性能瓶颈，并详细介绍如何通过排序和双指针技术构建一个时间复杂度更优的解决方案。文章将提供清晰的代码示例，并解析其时间复杂度，帮助读者掌握高效处理数组求和问题的技巧，尤其是在避免重复结果方面的策略。

1. 问题描述

“三数之和”问题（3Sum）要求从一个整数数组 nums 中找出所有唯一的三元组 [nums[i], nums[j], nums[k]]，使得 i != j、i != k、j != k，并且 nums[i] + nums[j] + nums[k] == 0。解决方案中不能包含重复的三元组。

2. 超时解法分析

原始代码尝试通过排序和嵌套的搜索函数来解决问题。虽然在小规模测试用例上可能有效，但在处理大规模或特定边缘情况时，会因为时间复杂度过高而导致“超出时间限制”（Time Limit Exceeded）。

让我们分析一下原始代码的结构和潜在的性能瓶颈：

def threeSum(nums):
    sol = []
    pos = 1
    nums.sort() # O(N log N)

    def search(p, vals): # vals 是 nums 的副本
        l, r = 0, len(vals) - 1
        sols = []
        while l < p < r:
            if vals[l] + vals[p] + vals[r] == 0:
                sols.append([vals[l], vals[p], vals[r]])
                # 关键问题：pop 操作
                vals.pop(r) # O(N)
                vals.pop(l) # O(N)
                l, r = l, r - 2
                p -= 1
                continue
            if vals[l] + vals[p] + vals[r] > 0:
                r -= 1
            if vals[l] + vals[p] + vals[r] < 0:
                l += 1
        return sols

    while pos < len(nums) - 1: # 外层循环 O(N)
        new_sol = search(pos, nums[:]) # 关键问题：切片操作 O(N)
        for n in new_sol: # 内层循环
            if n not in sol: # 关键问题：in 操作 O(K) K为sol长度
                sol.append(n)
        pos += 1
    return sol

性能瓶颈：

1. nums[:] 切片操作： 在每次 while pos 循环中，search 函数都接收 nums[:] 作为参数，这意味着每次调用都会创建一个 nums 数组的完整副本。这个操作的时间复杂度是 O(N)，导致外层 while pos 循环的整体复杂度至少为 O(N^2)。
2. vals.pop() 操作： 在 search 函数内部，当找到一个三元组时，会使用 vals.pop(r) 和 vals.pop(l) 来移除元素。对于 Python 列表，pop() 操作的平均时间复杂度是 O(1)，但 pop(index) （当 index 不是最后一个元素时）需要移动后续所有元素，因此其时间复杂度是 O(N)。这使得 search 函数内部的循环复杂度大大增加。
3. if n not in sol: 查重： 在外层循环中，通过 n not in sol 来检查新找到的三元组是否已存在。由于 sol 可能包含多个三元组，in 操作的平均时间复杂度是 O(K)，其中 K 是 sol 的长度。在最坏情况下，sol 的长度可以达到 O(N^2)，使得这个查重操作变得非常昂贵。

综合来看，这些操作导致了原始解决方案的时间复杂度远超 O(N^2)，很可能达到 O(N^4) 甚至更高，因此在面对大量测试数据时会超时。

无限画

千库网旗下AI绘画创作平台

574 查看详情

3. 高效解法：排序与双指针

解决三数之和问题的标准高效方法是结合排序和双指针技术。这种方法能够将时间复杂度优化到 O(N^2)，并且能有效处理重复三元组的问题。

3.1 核心思想

1. 排序数组： 首先对输入的数组 nums 进行排序。排序是 O(N log N) 的操作，但它为后续的双指针查找提供了便利。
2. 固定一个元素： 遍历排序后的数组，依次将每个元素 nums[i] 作为三元组的第一个元素。
3. 双指针查找： 对于每个固定的 nums[i]，在 i 之后的子数组中使用两个指针 lo 和 hi 来寻找另外两个元素 nums[lo] 和 nums[hi]，使得 nums[i] + nums[lo] + nums[hi] == 0。
   • lo 指针从 i + 1 开始。
   • hi 指针从数组末尾 len(nums) - 1 开始。
4. 跳过重复元素： 为了确保最终结果中不包含重复的三元组，在遍历 i 以及移动 lo 和 hi 指针时，需要跳过与前一个元素相同的元素。

3.2 步骤详解

1. 初始化：
   • 创建一个空列表 unique_triplets 用于存储结果。
   • 对 nums 数组进行升序排序。
2. 外层循环（固定 nums[i]）：
   • 遍历 i 从 0 到 len(nums) - 3（因为需要至少三个元素）。
   • 优化：提前终止 如果 nums[i] > 0，则由于数组已排序，后续的 nums[lo] 和 nums[hi] 也将是非负数，三数之和不可能为零，因此可以直接中断循环。
   • 去重： 如果 i > 0 且 nums[i] == nums[i-1]，说明当前的 nums[i] 与上一个 nums[i-1] 相同，这将导致重复的三元组，所以跳过当前 i 的迭代。
3. 内层循环（双指针 lo 和 hi）：
   • 设置 lo = i + 1 和 hi = len(nums) - 1。
   • 在一个 while lo
   • 计算当前三数之和 current_sum = nums[i] + nums[lo] + nums[hi]。
   • 如果 current_sum 说明和太小，需要增大，因此 lo += 1。
   • 如果 current_sum > 0： 说明和太大，需要减小，因此 hi -= 1。
   • 如果 current_sum == 0： 找到了一个符合条件的三元组。
     • 将 [nums[i], nums[lo], nums[hi]] 添加到 unique_triplets 中。
     • 去重： 为了避免 nums[lo] 和 nums[hi] 产生重复的三元组，需要继续移动 lo 和 hi 指针，直到它们指向的元素与前一个不同。
       • while lo
       • while lo
     • 然后，正常移动 lo += 1 和 hi -= 1，继续寻找下一个可能的三元组。

3.3 代码实现

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    unique_triplets = []
    nums.sort() # O(N log N)

    # 遍历 i 作为第一个元素
    for i in range(len(nums) - 2):
        # 优化：如果当前 nums[i] 已经大于 0，则后续不可能找到和为 0 的三元组
        if nums[i] > 0:
            break

        # 去重：跳过重复的 nums[i]
        # 如果当前元素与前一个元素相同，则会产生重复的三元组，跳过
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 使用双指针查找剩余的两个元素
        lo = i + 1
        hi = len(nums) - 1

        while lo < hi:
            current_sum = nums[i] + nums[lo] + nums[hi]

            if current_sum < 0:
                lo += 1 # 和太小，增大 lo
            elif current_sum > 0:
                hi -= 1 # 和太大，减小 hi
            else: # current_sum == 0，找到一个三元组
                unique_triplets.append([nums[i], nums[lo], nums[hi]])

                # 去重：跳过重复的 nums[lo] 和 nums[hi]
                # 移动 lo 指针，直到它指向的元素与当前不同
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                # 移动 hi 指针，直到它指向的元素与当前不同
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1

                # 正常移动指针，继续寻找下一个三元组
                lo += 1
                hi -= 1
    return unique_triplets

4. 时间复杂度分析

• 原始超时解法：

  • nums.sort(): O(N log N)
  • 外层 while pos 循环：O(N)
  • nums[:] 切片：O(N)
  • search 函数内部的 pop(index)：O(N)
  • if n not in sol:：最坏情况下 O(N^2)
  • 综合来看，由于多次 O(N) 操作嵌套在 O(N^2) 的结构中，整体复杂度可能接近 O(N^4) 甚至更高。

• 优化后的双指针解法：

  • nums.sort()：O(N log N)。这是整个算法的初始成本。
  • 外层 for i 循环：O(N)。
  • 内层 while lo
  • 跳过重复元素的 while 循环：这些 while 循环虽然看起来是嵌套的，但 lo 和 hi 指针在整个内层循环中只会向中间移动，总的移动次数不会超过 O(N)。因此，它们并不会增加内层循环的渐进时间复杂度。
  • 整体时间复杂度： O(N log N)（排序） + O(N N)（外层循环 内层双指针）。因此，总的时间复杂度是 O(N^2)。
  • 空间复杂度： O(1)（如果忽略存储结果列表的空间，只考虑辅助空间），或者 O(N)（如果考虑结果列表可能存储 N 个三元组）。

5. 注意事项与优化点

1. 排序的必要性： 排序是双指针方法的基础，它使得我们可以有序地移动指针，并轻松判断和的大小。同时，它也简化了去重逻辑。
2. 去重策略：
   • 外层 i 的去重： if i > 0 and nums[i] == nums[i - 1]: continue 确保第一个元素不重复。
   • 内层 lo 和 hi 的去重： while lo
3. 提前终止： if nums[i] > 0: break 是一个重要的剪枝操作。如果数组已排序，当第一个元素 nums[i] 已经大于 0 时，由于后续元素也都是非负数，它们的和不可能为 0，可以直接结束循环，进一步优化性能。

6. 总结

LeetCode 的“三数之和”问题是一个经典的算法题，它很好地展示了如何通过结合排序和双指针技术来优化解决方案。从一个直观但低效的暴力（或接近暴力）解法，通过识别并消除昂贵的操作（如列表切片、pop 移除和 in 查重），可以将其时间复杂度从 O(N^4) 甚至更高降低到高效的 O(N^2)。理解并掌握这种模式对于解决其他类似的数组求和问题（如两数之和、四数之和）至关重要。

以上就是优化LeetCode三数之和问题：从超时到高效的两指针解法的详细内容，更多请关注其它相关文章！

# 解决问题  # 提供网站建设策略的好处  # 河北网站建设推广运营  # 网络推广营销品牌  # 东坑网站关键词优化费用  # 12306的网站建设  # 邯郸网站建设设计公司  # 电商运营网站建设方案  # 益智玩具店营销推广策略  # 江东区网站优化报价  # 潞城网站如何做优化  # 太小  # python  # 可以直接  # 太大  # 浮点  # 是一个  # 更高  # 遍历  # 第一个  # 跳过  # elif  # 性能瓶颈  # app 

相关栏目： 【 Google疑问12 】 【 Facebook疑问10 】 【 优化推广96088 】 【 技术知识133117 】 【 IDC资讯59369 】 【 网络运营7196 】 【 IT资讯61894 】

相关推荐： Excel如何快速合并单元格内容_Excel文本合并与函数操作技巧  Linux如何自动分析系统异常日志_Linux日志智能检测  PHP动态导航按钮：根据用户登录状态切换链接与文本  Microsoft Edge网页字体太淡看不清怎么办_Microsoft Edge字体渲染优化技巧  优化CSS动画与J*aScript定时器协同：构建稳定Toast提示  快递优选如何查优选物流_快递优选专属物流渠道查询与配送时效  Teambition网盘如何共享文件  苹果17 Pro如何启用分屏浏览_iPhone 17 Pro分屏浏览设置步骤  抖音赚钱快速入门_新手必看的抖音赚钱步骤  Animex动漫社社登录官网 Animex动漫社资源社入口直达  iPhone 13 Pro Max如何设置桌面小组件_iPhone 13 Pro Max小组件添加指南  如何自定义苹果手机铃声  《伊瑟》凶影追缉库卢鲁boss攻略  魔法祈幻界兑换码礼包大全  126邮箱申请入口官网_126邮箱注册免费登录2025  鸣潮历史学家灯塔位置一览  使用 .htaccess 正确配置 WordPress 子目录重定向与路径保留  百度浏览器无法安装扩展程序_百度浏览器插件安装失败原因解析  Python模块化编程：避免循环导入与共享函数的最佳实践  汽水音乐官网网页版入口 汽水音乐官网网页版在线入口  《随手记》启用语音备注方法  雨课堂官网在线登录 网页版雨课堂登录链接  电脑开不了机怎么办 电脑无法开机的解决方法  《新三国志曹操传》游历事件袁尚突围攻略  iPhone14无法连接蓝牙设备如何解决  《淘宝联盟》推广自己的店铺方法  解决J*aScript动态图片上传中ID重复问题：在同一页面显示多张独立图片  《猎聘》筛选猎头岗位方法  教育查询官方网站入口 教育个人档案查询免费官网  批改网网页版登录 批改网电脑版学生登录入口  如何查找哪个composer包引入了特定的依赖？  悟空浏览器网页版链接 悟空浏览器网页版最新有效地址  《绝区零》2.3前瞻|直播|内容介绍  电脑“无法访问指定设备、路径或文件”怎么办？五种权限设置方法  《东方财富》条件单关闭方法  mysql如何管理数据库账户_mysql数据库账户管理技巧  CSS如何在页面中引入重置样式_使用Normalize.css或Reset.css统一浏览器默认样式  MySQL多重关联查询：利用别名高效获取同一表的多个关联字段  uc浏览器官网网页版使用 uc浏览器官网免费在线首页  J*a中导出MySQL表为SQL脚本的两种方法  《火影忍者：木叶高手》快速升级攻略  顺丰快递怎么查物流_顺丰快递物流信息实时查询操作指南  店铺如何关联视频号推广？视频号推广有什么用？  小米手机屏幕失灵乱跳怎么办 屏幕触控问题自检与临时解决方法【应急】  解决jQuery多计算器输入字段冲突的教程  小红书网页版怎么进 小红书网页版通用入口  mysql触发器如何编写_mysql触发器编写规范与代码示例讲解  申通快件单号查询平台 申通包裹物流动态跟踪  植物大战僵尸95版游戏版下载_植物大战僵尸95版游戏版安装指南  Python测试中模块导入路径解析的最佳实践 

 2025-11-17