优化LeetCode 3Sum问题：从超时到高效双指针解法

本文深入探讨leetcode 3sum问题，分析常见超时解法的时间复杂度瓶颈，并详细介绍如何通过排序和双指针技术将其优化至o(n^2)。文章将提供一个高效的python实现，并解释如何有效处理重复元素，确保生成唯一三元组，最终实现性能的显著提升。

理解 3Sum 问题

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

分析低效解法及其时间复杂度瓶颈

一个常见的初步思路可能是对数组进行排序，然后通过某种方式遍历寻找满足条件的三元组。然而，如果处理不当，很容易导致时间复杂度过高。

考虑以下一种尝试解决此问题的Python代码：

def threeSum_inefficient(nums):
    sol = []
    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]])
                # 这里的pop操作在列表中是O(N)
                vals.pop(r) 
                vals.pop(l)
                l, r = l, r - 2
                p -= 1
                continue
            if current_sum > 0:
                r -= 1
            if current_sum < 0:
                l += 1
        return sols

    pos = 1
    while pos < len(nums) - 1: # 外层循环O(N)
        # nums[:] 创建了列表的副本，O(N)
        new_sol = search(pos, nums[:]) 
        for n in new_sol:
            # `n not in sol` 检查可能需要O(K*L) 其中K是sol的长度，L是三元组的长度
            if n not in sol: 
                sol.append(n)
        pos += 1
    return sol

时间复杂度分析：

1. 排序： nums.sort() 的时间复杂度为 O(N log N)。
2. 外层 while 循环： 循环 pos 变量，执行 N 次。
3. 列表复制： 在每次外层循环中，nums[:] 会创建一个新的列表副本，这需要 O(N) 的时间。
4. search 函数： 内部的 while 循环在最坏情况下会执行 O(N) 次。
5. pop 操作： 在 search 函数内部，vals.pop(r) 和 vals.pop(l) 操作会改变列表结构，在Python中，从列表中间或头部删除元素通常需要 O(N) 的时间来移动后续元素。
6. 重复性检查： if n not in sol: 语句在 sol 列表中查找 n，如果 sol 中有 K 个元素，每个元素比较需要 O(L) (L是三元组长度)，则此操作最坏情况下是 O(K * L)。由于 K 最大可达 O(N^3)，这会带来巨大的开销。

综合来看，这种方法由于频繁的列表复制、pop 操作以及低效的重复检查，其时间复杂度可能远超 O(N^3)，导致在大型测试用例上出现“时间限制超出” (Time Limit Exceeded)。

高效解法：排序与双指针技术

解决 3Sum 问题的标准高效方法是结合排序和双指针技术。核心思想是：

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

22

查看详情

1. 排序数组： 首先对数组 nums 进行排序，这使得我们可以更容易地处理重复元素，并利用元素的有序性。
2. 固定一个元素： 遍历数组，固定一个元素 nums[i] 作为三元组的第一个元素。
3. 双指针查找： 对于固定的 nums[i]，在 nums[i+1:] 这个子数组中使用双指针（lo 和 hi）来寻找另外两个元素，使得 nums[i] + nums[lo] + nums[hi] == 0。
   • lo 指针从 i+1 开始。
   • hi 指针从数组末尾 (len(nums) - 1) 开始。
   • 根据 nums[i] + nums[lo] + nums[hi] 的和与 0 的比较结果移动 lo 或 hi。
     • 如果和小于 0，说明需要更大的值，lo 右移。
     • 如果和大于 0，说明需要更小的值，hi 左移。
     • 如果和等于 0，则找到一个有效三元组，将其添加到结果中，然后 lo 右移，hi 左移，并跳过重复元素。

Python 实现与代码解析

以下是采用排序和双指针技术的高效Python实现：

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    unique_triplets = []
    nums.sort()  # O(N log N) 排序是第一步，也是后续双指针法的基础

    # 遍历数组，固定第一个元素 nums[i]
    # 循环到 len(nums) - 2 是因为需要至少两个后续元素 (lo 和 hi)
    for i in range(len(nums) - 2):
        # 避免重复的第一个元素
        # 如果当前元素与前一个元素相同，则跳过，因为它们会生成重复的三元组
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 初始化双指针
        lo = i + 1  # lo 指针从 i 的下一个位置开始
        hi = len(nums) - 1 # hi 指针从数组末尾开始

        # 双指针循环，在 nums[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 必须移动以寻找新的组合
                # 如果 lo 指向的下一个元素与当前元素相同，则继续右移 lo，直到指向不同的元素
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                # 跳过重复的 hi 元素
                # 同样，如果 hi 指向的前一个元素与当前元素相同，则继续左移 hi
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1

                # 移动指针以寻找下一个可能的组合
                lo += 1
                hi -= 1

    return unique_triplets

代码解析要点：

1. 排序 (nums.sort()): 这是解决此问题的关键第一步，将数组变为有序，为双指针法创造条件。
2. 外层循环 (for i in range(len(nums) - 2)): 固定三元组的第一个元素 nums[i]。len(nums) - 2 确保 lo 和 hi 至少有两个元素可以指向。
3. 跳过重复的 nums[i] (if i > 0 and nums[i] == nums[i - 1]): 这一步非常重要，它确保我们不会处理相同的 nums[i] 多次，从而避免生成重复的三元组。例如，如果数组是 [-1, -1, 0, 1, 2]，当 i 第一次指向 -1 时，我们处理它。当 i 第二次指向 -1 时，我们应该跳过，因为用它作为第一个元素会得到与前一次相同的组合。
4. 双指针 (lo, hi): lo 从 i+1 开始，hi 从数组末尾开始。它们在 nums[i+1...len(nums)-1] 范围内搜索。
5. 和的判断与指针移动：
   • target_sum < 0: 需要更大的和，lo 右移。
   • target_sum > 0: 需要更小的和，hi 左移。
   • target_sum == 0: 找到一个有效三元组。将其添加到结果列表。
6. 跳过重复的 nums[lo] 和 nums[hi] (while lo < hi and nums[lo] == nums[lo + 1] 等): 在找到一个有效三元组后，我们需要移动 lo 和 hi 指针。如果 lo 或 hi 指向的下一个（或上一个）元素与当前元素相同，我们需要跳过这些重复元素，否则会生成重复的三元组。例如，对于 [-2, 0, 0, 2, 2]，当 nums[i] = -2, nums[lo] = 0, nums[hi] = 2 得到 [-2, 0, 2] 后，如果 lo 只是简单地加一，会再次得到 [-2, 0, 2]。因此需要跳过第二个 0。

时间复杂度分析

• 排序： nums.sort() 的时间复杂度是 O(N log N)。
• 外层循环： for i in range(len(nums) - 2) 循环执行 N 次。
• 内层双指针循环： while lo < hi 循环在最坏情况下，lo 和 hi 指针总共会遍历 O(N) 个元素。
• 跳过重复元素： 内部的 while 循环虽然看起来是嵌套的，但 lo 和 hi 指针在整个内层循环中只会单向移动，最多移动 O(N) 次。

综合来看，外层循环 O(N) 乘以内层双指针循环 O(N)，总计为 O(N^2)。加上排序的 O(N log N)，最终的时间复杂度是 O(N log N + N^2)，简化为 O(N^2)。

空间复杂度： 除了存储结果列表 unique_triplets 所需的空间（最坏情况下 O(N)，因为最多有 O(N^2) 个三元组，但通常是 O(1) 如果不计算输出空间），以及排序可能使用的辅助空间（取决于排序算法，通常为 O(log N) 或 O(N)），算法本身只使用了常数额外的空间，所以空间复杂度为 O(1)（不计输出）。

总结与注意事项

• 排序是基石： 解决 3Sum 及类似多和问题时，对数组进行排序通常是第一步，它能简化后续的重复处理和双指针逻辑。
• 双指针的威力： 在固定一个或两个元素后，利用双指针技术在有序子数组中寻找目标和，可以将复杂度从 O(N^2) 降至 O(N)，从而将整体复杂度从 O(N^3) 降至 O(N^2)。
• 精细处理重复元素： 这是 3Sum 问题的一个难点。必须在外层循环（跳过重复的 nums[i]）和内层双指针循环（跳过重复的 nums[lo] 和 nums[hi]）中都进行处理，以确保结果集中不包含重复的三元组。
• 避免昂贵操作： 避免在循环内部进行列表的 pop、insert 或创建大量副本等 O(N) 操作，这些操作会显著增加整体时间复杂度。

通过理解和应用排序与双指针技术，我们可以高效地解决 3Sum 问题，避免常见的“时间限制超出”错误。

以上就是优化LeetCode 3Sum问题：从超时到高效双指针解法的详细内容，更多请关注php中文网其它相关文章！