博客

Python三数之和的实现方式

三数之和是一道经典的算法问题，其目标是在一个数组中找到三个数，使它们和为0。本文将介绍两种Python实现三数之和的方法。

方法一：暴力枚举

最简单的方法是使用重循环枚举所有可能的三元组，并检查它们的和是否为0。这种方法的时间复杂度为O(n^3)，不用于大型数组。

下面是一个示例，用于演示如何使用暴力枚举实现三数之和。

def three_sum(nums):
    res = []
    nums.sort()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, len(nums) - 1):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            for k in range(j+1, len(nums)):
                if k > j+1 and nums[k] == nums[k-1]:
                    continue
                if nums[i] + nums[j] + nums[k] == 0:
                    res.append([nums[i], nums[j], nums[k]])
    return res

在这个示例中，我们定义了一个three_sum()函数，它接受一个整数数组作为参数，并返回一个包含所有三元组的列表，使它们的和为0。我们首先对数组进行排序，然后使用三重循环枚举所有可能的三元组。我们还使用一些技巧来避免重复计算，例如跳过相同的元素和跳过已经计算过的三元组。

方法二：双指针法

另一种更高效的方法是使用双指针法。我们首先对数组进行排序，然后使用两重循环枚举前两个数。对于每个前两个数，我们使用双指针法在剩余的数组中查找第三个数。由于数组已经排序，我们可以使用左右指针分别从数组的两端开始向中间移动，直到找到一个和为0的三元组或者左右指针相遇。

下面是一个示例，用于演示如何使用双指针法实现三数之和。

def three_sum(nums):
    res = []
    nums.sort()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i+1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
    return res

在这个示例中，我们定义了一个three_sum()函数，它接受一个整数数组作为参数，并返回一个包含所有三元组的列表，使它们的和为0。我们首先对数组进行排序，然使用两重循环枚举前两个数。对于每个前两个数，我们使用双指针法在剩余的数组中查找第三个数。我们还使用一些技巧来避免重复计算，例如跳过相同的元素和跳过已经计算过的三元组。

结论

本文介绍了两种Python实现三数之和的方法：暴力枚举和双指针法。暴力枚举的时间复杂度为O(n^3)，不适用于大型数组。双指针法的时间复杂度为O(n^2)，适用于大型数组。在实际应用中，我们可以根据具体的问题选择不同的方法，结合其他数据结构和算法进行合理处理，实现复杂的计算任务的求解。