优化Python中的三数之和问题：从超时到高效解决方案

本文深入探讨leetcode三数之和问题，分析常见超时解决方案的性能瓶颈，并详细介绍一种基于排序和双指针技术的优化算法。通过代码示例和复杂度分析，读者将掌握如何高效地在给定整数数组中找出所有和为零的唯一三元组，避免重复并达到最优时间复杂度。

1. 问题概述

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

2. 初步尝试与性能瓶颈分析

在解决此类问题时，一个直观的思路可能是通过多层循环来枚举所有可能的三元组。然而，简单的三层循环通常会导致 O(N^3) 的时间复杂度，这对于较大规模的输入数据会超出时间限制。

考虑以下一个尝试解决该问题的Python代码示例：

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

    def search(p, vals):
        l, r = 0, len(vals) - 1
        sols = []
        while l < p < r:
            current_sum = vals[l] + vals[p] + vals[r]
            if current_sum == 0:
                sols.append([vals[l], vals[p], vals[r]])
                # 以下操作是主要的性能瓶颈
                vals.pop(r) # O(N)
                vals.pop(l) # O(N)
                r -= 2
                p -= 1
                continue
            if current_sum > 0:
                r -= 1
            if current_sum < 0:
                l += 1
        return sols

    while pos < len(nums) - 1: # O(N)
        new_sol = search(pos, nums[:]) # nums[:] O(N)
        for n in new_sol: # 最坏情况下 O(N^3) 个三元组
            if n not in sol: # O(k) for list lookup, where k is len(sol)
                sol.append(n)
        pos += 1
    return sol

时间复杂度分析：

立即学习“Python免费学习笔记（深入）”；

1. 排序 nums.sort(): 这一步的时间复杂度是 O(N log N)。
2. 外层 while 循环: 循环 pos 大约 N 次。
3. nums[:] 切片: 在每次外层循环中，nums[:] 会创建一个新的列表副本，其时间复杂度为 O(N)。
4. 内层 search 函数:
   • while l < p < r 循环在最坏情况下会迭代 O(N) 次。
   • 在 current_sum == 0 的分支中，vals.pop(r) 和 vals.pop(l) 操作会从列表中删除元素。在Python列表中，删除任意位置的元素（特别是头部或中间）会导致其后所有元素移动，因此每次 pop 操作的时间复杂度是 O(N)。
   • 这意味着 search 函数内部的 pop 操作使得其最坏情况下的时间复杂度达到 O(N^2)。
5. for n in new_sol: if n not in sol::
   • new_sol 最坏情况下可能包含 O(N^3) 个三元组（尽管实际上会少很多）。
   • n not in sol 检查操作在Python列表中是线性的，时间复杂度为 O(k)，其中 k 是 sol 列表的长度。在最坏情况下，sol 列表可能增长到 O(N^3) 大小，导致 O(N^3) 的查找时间。

综合来看，threeSum_initial 函数的整体时间复杂度将远超 O(N^3)，尤其受到 pop 操作和 in 关键字查找重复三元组的影响，使其在面对大数据集时极易超时。

OmniAudio

OmniAudio 是一款通过 AI 支持将网页、Word 文档、Gmail 内容、文本片段、视频音频文件都转换为音频播客，并生成可在常见 Podcast ap

111

查看详情

3. 优化策略：排序与双指针

为了高效解决三数之和问题，我们通常采用“排序 + 双指针”的策略。

1. 排序: 首先对数组进行排序。排序后的数组有助于我们快速判断和调整指针，以及有效地跳过重复元素。
2. 固定一个元素: 遍历排序后的数组，依次固定一个元素 nums[i] 作为三元组的第一个元素。
3. 双指针查找: 对于每一个固定的 nums[i]，我们需要在 nums[i+1:] 这个子数组中找到另外两个元素 nums[lo] 和 nums[hi]，使得 nums[lo] + nums[hi] == -nums[i]（即 nums[i] + nums[lo] + nums[hi] == 0）。
   • 设置两个指针 lo (低位指针) 和 hi (高位指针)，分别指向 i+1 和 len(nums)-1。
   • 计算 current_sum = nums[i] + nums[lo] + nums[hi]。
   • 如果 current_sum < 0，说明和太小，需要增大，因此 lo += 1。
   • 如果 current_sum > 0，说明和太大，需要减小，因此 hi -= 1。
   • 如果 current_sum == 0，则找到了一个有效的三元组。将其添加到结果集中，然后 lo += 1 且 hi -= 1，继续寻找其他可能的三元组。
4. 去重: 在上述过程中，需要特别注意处理重复的三元组。
   • 固定元素 nums[i] 的去重: 如果 nums[i] 与 nums[i-1] 相同，则跳过当前的 i，因为以 nums[i-1] 开头的三元组已经考虑过，这将避免生成重复的三元组。
   • 双指针 lo 和 hi 的去重: 当找到一个有效三元组后，lo 和 hi 都需要移动。在移动之前，需要检查 nums[lo] 是否与 nums[lo+1] 相同，以及 nums[hi] 是否与 nums[hi-1] 相同。如果相同，则跳过这些重复的元素，直到遇到不同的元素为止，以避免生成重复的三元组。

4. 高效解决方案的实现

以下是基于排序和双指针策略的优化Python代码：

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    unique_triplets = []
    nums.sort() # 首先对数组进行排序

    # 遍历数组，固定第一个元素 nums[i]
    # 只需要遍历到倒数第三个元素，因为至少需要两个元素给 lo 和 hi
    for i in range(len(nums) - 2):
        # 避免重复的第一个元素
        # 如果当前元素与前一个元素相同，则跳过，因为以 nums[i-1] 开头的三元组已经处理过
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 设置双指针
        lo = i + 1          # 低位指针从 i+1 开始
        hi = len(nums) - 1  # 高位指针从数组末尾开始

        # 在 lo < hi 的范围内寻找另外两个元素
        while lo < hi:
            target_sum = nums[i] + nums[lo] + nums[hi]

            if target_sum < 0:
                # 和小于0，说明 lo 指向的数字太小，需要增大
                lo += 1
            elif target_sum > 0:
                # 和大于0，说明 hi 指向的数字太大，需要减小
                hi -= 1
            else: # target_sum == 0，找到一个有效三元组
                unique_triplets.append([nums[i], nums[lo], nums[hi]])

                # 避免重复的 lo 元素
                # 在找到一个有效三元组后，lo 和 hi 都要移动，同时跳过所有重复的元素
                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

5. 时间复杂度分析

1. 排序: nums.sort() 的时间复杂度是 O(N log N)。
2. 外层循环: for i in range(len(nums) - 2) 循环 N 次。
3. 内层 while 循环 (双指针): 对于每个 i，lo 和 hi 指针会从两端向中间移动，在最坏情况下，它们会遍历 N 个元素。因此，内层双指针循环的时间复杂度是 O(N)。
4. 去重操作: 内部的 while 循环用于跳过重复元素，它们只是在 lo 和 hi 移动的基础上进行，并不会增加额外的 N 因子，因此仍属于 O(N) 的范畴。

综合来看，总的时间复杂度为 O(N log N + N * N)，简化为 O(N^2)。这比原始的 O(N^3) 甚至更高的时间复杂度有了显著的提升。

6. 空间复杂度分析

1. unique_triplets 列表: 在最坏情况下，可能会找到 O(N^3) 个三元组（例如，对于 [-2, -1, 0, 1, 2] 这样的数组，如果允许重复，但由于去重，实际存储的唯一三元组数量通常远小于 N^3）。然而，根据数学分析，对于 N 个元素的数组，最多可以有 O(N^2) 个不同的三元组。因此，存储结果的空间复杂度是 O(N^2)。
2. 排序: Python 的 sort() 方法（Timsort）在大多数情况下是原地排序，空间复杂度为 O(log N) 或 O(N)（取决于具体实现和数据特性，但通常被认为是 O(log N)）。

综合来看，总的空间复杂度主要取决于存储结果的列表，为 O(N^2)。

7. 总结与注意事项

• 排序的重要性: 对数组进行排序是使用双指针技术的前提，它使得我们可以有序地调整指针，并方便地处理重复元素。
• 双指针的效率: 双指针技术将内层循环的时间复杂度从 O(N) 降低到 O(1)（每次迭代），从而将整体复杂度从 O(N^3) 优化到 O(N^2)。
• 去重是关键: 在三数之和这类问题中，处理重复元素是算法正确性和效率的关键。无论是固定元素的去重，还是双指针移动时的去重，都必须仔细考虑。
• 边界条件: 注意循环的边界条件，例如 for i in range(len(nums) - 2)，确保 lo 和 hi 始终有足够的元素可以指向。

通过掌握这种“排序 + 双指针”的模式，可以高效地解决许多类似的数组查找问题，例如两数之和、四数之和等。

以上就是优化Python中的三数之和问题：从超时到高效解决方案的详细内容，更多请关注php中文网其它相关文章！