Python查找固定和的数字三元组：暴力法与优化对比

一、问题模型与算法挑战

固定和三元组问题的标准表述为：给定一个包含 n 个整数的数组 nums 以及一个目标和 target，需要在数组中找到所有的三元组 [nums[i], nums[j], nums[k]]，使得 nums[i] + nums[j] + nums[k] == target，并且满足索引互不相同（即 i < j < k）。

在实际工程或面试考核中，该问题通常伴随以下两个关键限制：

• 结果不可重复：如果数组中存在多个数值相同的元素，可能组合出数值完全一致的三元组，输出结果必须去除重复组合；
• 计算规模约束：当数组长度 n 达到数千量级时，未经优化的组合搜索会导致执行耗时急剧上升甚至超时崩溃。

二、暴力枚举法：原理与实现

暴力法（Brute Force）是最直观的求解策略。它的思路是构建三层嵌套循环，依次枚举数组中所有可能的三元素下标组合 (i, j, k)，检查其元素和是否与 target 相等。为了防止提取出由相同元素打乱顺序形成的重复三元组，通常对找到的三元组进行排序后加入集合（Set）进行去重。

1. 完整代码示例

def find_three_sum_brute_force(nums: list[int], target: int) -> list[list[int]]:
    """
    使用三重循环暴力查找所有和为 target 的三元组
    时间复杂度: O(n^3)
    空间复杂度: O(k), k 为符合条件的三元组数量
    """
    n = len(nums)
    res_set = set()
    
    # 三层循环枚举所有不重复索引的组合
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    # 将三元组排序后转换为元组存入 set 去重
                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    res_set.add(triplet)
                    
    # 转换回列表格式输出
    return [list(item) for item in res_set]

# 运行示例
if __name__ == "__main__":
    test_nums = [-1, 0, 1, 2, -1, -4]
    target_sum = 0
    result = find_three_sum_brute_force(test_nums, target_sum)
    print("暴力法输出结果:", result)
    # 示例输出: [[-1, 0, 1], [-1, -1, 2]]

2. 局限性与性能瓶颈

暴力法的数学组合总数为数学中的组合数 C(n, 3) = n(n - 1)(n - 2) / 6。当数组元素个数逐渐增加时，计算步数呈现三次方的爆炸式增长：

• 当 n = 100 时，三元组检查次数约为 1.6×10⁵ 次，现代计算机可在毫秒内完成；
• 当 n = 1,000 时，检查次数激增至 1.6×10⁸ 次，Python 解释器执行耗时将达到秒级；
• 当 n = 10,000 时，检查次数高达约 1.6×10¹¹ 次，无论如何优化循环体都将面临灾难性的超时。

三、双指针优化法：排序与降维原理

要想打破 O(n³) 的时间壁垒，核心思想是利用数组的有序单调性将内层两重循环降解为单层扫描。

具体算法分为三个严密递进的执行步骤：

1. 全量升序排序：耗费 O(n log n) 时间将数组从小到大排列。排序不仅为指针移动提供了方向指示，也为后续连续重复元素的跳过奠定了基础；
2. 固定第一元素：遍历下标 i 从 0 到 n-3，令基准数为 nums[i]。此时问题转化为在右侧子区间中寻找两个数字，使其和等于 target - nums[i]；
3. 双指针向中夹逼：初始化左指针 left = i + 1（指向区间最小值），右指针 right = n - 1（指向区间最大值）：
   • 若 current_sum == target：找到合法解，记录三元组，同时推进 left 和 right，并跳过相同的相邻元素；
   • 若 current_sum < target：说明数值偏小，唯有增大较小数才能逼近目标，因此执行 left += 1；
   • 若 current_sum > target：说明数值偏大，唯有减小较大数才能逼近目标，因此执行 right -= 1。

1. 完整代码实现（包含去重与剪枝）

def find_three_sum_optimized(nums: list[int], target: int) -> list[list[int]]:
    """
    排序 + 双指针优化查找固定和三元组
    时间复杂度: O(n^2)
    空间复杂度: O(1) (忽略排序系统栈开销)
    """
    n = len(nums)
    if n < 3:
        return []
        
    # 第一步：原址升序排序
    nums.sort()
    result = []
    
    # 第二步：固定基准元素 i
    for i in range(n - 2):
        # 优化剪枝 1: 如果当前数字与前一个相同，跳过以避免外层重复解
        if i > 0 and nums[i] == nums[i - 1]:
            continue
            
        # 优化剪枝 2: 如果当前数与随后两个最小数相加已大于目标，后续循环无法达成目标，直接终止
        if nums[i] + nums[i + 1] + nums[i + 2] > target:
            break
            
        # 优化剪枝 3: 如果当前数与最大的两数相加仍小于目标，当前基准数偏小，尝试下一个基准数
        if nums[i] + nums[n - 2] + nums[n - 1] < target:
            continue
            
        # 第三步：左右双指针两端扫描
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # 关键去重: 连续跳过数值相等的 left 指针
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # 关键去重: 连续跳过数值相等的 right 指针
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                    
                # 收缩窗口
                left += 1
                right -= 1
                
            elif current_sum < target:
                left += 1
            else:
                right -= 1
                
    return result

# 运行验证
if __name__ == "__main__":
    test_cases = [
        ([-1, 0, 1, 2, -1, -4], 0),
        ([0, 0, 0, 0], 0),
        ([1, 2, -2, -1], 0)
    ]
    for arr, tgt in test_cases:
        res = find_three_sum_optimized(arr.copy(), tgt)
        print(f"输入: {arr}, 目标和: {tgt} => 输出: {res}")
    # 示例输出:
    # 输入: [-1, 0, 1, 2, -1, -4], 目标和: 0 => 输出: [[-1, -1, 2], [-1, 0, 1]]
    # 输入: [0, 0, 0, 0], 目标和: 0 => 输出: [[0, 0, 0]]
    # 输入: [1, 2, -2, -1], 目标和: 0 => 输出: []

四、两大法门核心对比与工程选型

在真实业务场景中选择算法，不能只看理论时间复杂度的渐近阶数，还需要综合评估输入规模、数据修改容忍度以及内存边界。

五、总结

在Python中解决“查找固定和数字三元组”这一问题，本质是探索如何在无序搜索空间中建立规则。暴力法虽然思路自然，但 O(n³) 的时间开销使其仅能作为小规模测试或基准校验手段。

通过引入升序排序，算法以仅仅 O(n log n) 的代价获得了元素的空间单调性，进而结合左右双指针将搜索维度压缩至 O(n²)。在此基础上，辅以边界剪枝与相邻元素去重检查，不仅彻底解决了内存泄漏式的哈希去重负担，也构成了面试考查与高频业务场景中最稳健的工业级实现方案。