Python基于for循环求解三数之和(Three Number Sum)问题

原有代码问题 #

• 采用三层嵌套循环实现，时间复杂度为O(n³)，属于性能最差的暴力解法
• 匹配到第一个符合条件的三元组后直接执行return终止函数，无法收集所有有效结果
• 结果列表初始化位置错误，每次外层循环都会重置空列表，无法累计多组结果

优化思路 #

采用预排序+双指针的两层循环方案，逻辑易理解，性能提升明显：

1. 先对数组做原地升序排序，利用有序特性简化后续查找逻辑，避免无意义遍历
2. 第一层for循环固定三元组的第一个数，遍历边界到数组倒数第三个元素即可，预留两个位置给剩余两个数
3. 对每个固定的第一个数，初始化左指针在其下一位、右指针在数组末尾，通过第二层循环移动指针：
   • 计算当前三数之和，若等于目标值，将三元组加入结果集，同时左指针右移、右指针左移查找下一组可能的组合
   • 若和小于目标值，说明总和偏小，左指针右移增大总和
   • 若和大于目标值，说明总和偏大，右指针左移减小总和

实现代码 #

def threeNumberSum(array, targetSum):
    array.sort()
    result = []
    arr_len = len(array)
    # 第一层循环固定第一个数
    for i in range(arr_len - 2):
        first_num = array[i]
        left = i + 1
        right = arr_len - 1
        # 第二层循环通过双指针查找剩余两个数
        while left < right:
            second_num = array[left]
            third_num = array[right]
            current_sum = first_num + second_num + third_num
            if current_sum == targetSum:
                result.append([first_num, second_num, third_num])
                left += 1
                right -= 1
            elif current_sum < targetSum:
                left += 1
            else:
                right -= 1
    return result

样例验证 #

传入题目给出的测试用例：

array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0
print(threeNumberSum(array, targetSum))

运行输出为[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]，和预期结果完全一致。

复杂度说明 #

• 时间复杂度：O(n²)，其中排序步骤耗时O(nlogn)，外层遍历O(n)，内层双指针单次遍历O(n)，远优于O(n³)的暴力实现
• 空间复杂度：O(1)，除结果存储外仅使用常数级额外变量，原地排序不会产生额外的线性空间开销

内容的提问来源于stack exchange，提问作者AXz