两指针法优化三数之和解法

最近发现不少小伙伴都对文章很感兴趣，所以今天继续给大家介绍文章相关的知识，本文《三数之和优化：两指针法告别超时》主要内容涉及到等等知识点，希望能帮到你！当然如果阅读本文时存在不同想法，可以在评论中表达，但是请勿使用过激的措辞~

本文深入探讨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) 甚至更高，因此在面对大量测试数据时会超时。

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 < hi 的循环中执行以下操作：
     • 计算当前三数之和 current_sum = nums[i] + nums[lo] + nums[hi]。
     • 如果 current_sum < 0： 说明和太小，需要增大，因此 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 < hi and nums[lo] == nums[lo + 1]: lo += 1
         • while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1
       • 然后，正常移动 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 < hi 循环：在最坏情况下，lo 和 hi 指针会遍历 O(N) 次。每次迭代中的操作（加法、比较、指针移动）都是 O(1)。
  • 跳过重复元素的 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 < hi and nums[lo] == nums[lo + 1]: lo += 1 和 while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1 确保在找到一个有效三元组后，lo 和 hi 移动到下一个不同的元素，避免添加重复的三元组。
3. 提前终止： if nums[i] > 0: break 是一个重要的剪枝操作。如果数组已排序，当第一个元素 nums[i] 已经大于 0 时，由于后续元素也都是非负数，它们的和不可能为 0，可以直接结束循环，进一步优化性能。

6. 总结

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

终于介绍完啦！小伙伴们，这篇关于《两指针法优化三数之和解法》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！