力扣 15 三数之和 (Three Sum)

问题描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a、b、c，使得 a + b + c = 0。请你找出所有满足条件且不重复的三元组。

示例

示例 1

输入：

plaintextCopy Code
nums = [-1, 0, 1, 2, -1, -4]

输出：

plaintextCopy Code
[[-1, -1, 2], [-1, 0, 1]]

示例 2

输入：

plaintextCopy Code
nums = []

输出：

plaintextCopy Code
[]

示例 3

输入：

plaintextCopy Code
nums = [0]

输出：

plaintextCopy Code
[]

问题分析

此问题的核心在于找到所有三元组，其中三个数的和为零，并且每个三元组在结果中只出现一次。具体地说，解决这个问题需要考虑以下几个方面：

1. 排序：为了高效地找到符合条件的三元组，我们首先对数组进行排序。这可以帮助我们使用双指针法在剩余的元素中寻找符合条件的两个数，从而优化算法的效率。

2. 去重：由于数组中可能存在重复的元素，所以我们在找到一个三元组后，需要确保它不会重复出现。可以通过跳过相同的元素来避免重复结果。

3. 双指针法：在数组排序之后，我们可以通过固定一个数，然后在剩余的数组中使用双指针查找另外两个数，使得它们的和为负的那个数的相反数。

解题思路

1. 排序：首先对数组进行排序。排序后，相同的数会相邻，可以通过跳过重复元素避免重复解。

2. 遍历数组：通过一个 for 循环遍历数组，并固定当前元素 nums[i]。然后通过双指针法，在数组的右侧部分查找两个数，使得这三个数的和为 0。

3. 双指针法：对于每个固定的数，使用两个指针，一个指向当前元素之后的位置（left），另一个指向数组的末尾（right）。根据这两个指针所指元素的和与目标值的关系，调整指针位置：

   • 如果三数之和大于 0，右指针左移；
   • 如果三数之和小于 0，左指针右移；
   • 如果三数之和等于 0，记录当前解并同时移动左右指针，以继续查找其他可能的解。

4. 跳过重复：在每次更新指针时，需要跳过重复的元素，以保证每个三元组都是唯一的。

解决方案

以下是具体的实现代码：

pythonCopy Code
def threeSum(nums):
    # 排序数组
    nums.sort()
    res = []
    
    # 遍历数组
    for i in range(len(nums) - 2):
        # 如果当前数大于0，则不可能找到三数和为0的情况，提前结束
        if nums[i] > 0:
            break
        # 跳过重复的元素，避免重复的三元组
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # 双指针初始化
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 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

复杂度分析

• 时间复杂度：首先对数组进行排序，时间复杂度为 O(n log n)，然后我们使用双指针法遍历数组，遍历过程中对每个元素做常数时间的操作。因此，总的时间复杂度为 O(n^2)，其中 n 为数组的长度。

• 空间复杂度：我们使用了一个额外的 res 数组来存储结果，最坏情况下需要存储所有可能的三元组，因此空间复杂度为 O(k)，其中 k 为三元组的数量。

解题案例

案例 1：输入 [-1, 0, 1, 2, -1, -4]

1. 排序：数组排序后为 [-4, -1, -1, 0, 1, 2]。
2. 遍历：
   • 固定第一个数 -4，双指针 left = 1，right = 5，求和 -4 + (-1) + 2 = -3，因为小于 0，所以左指针右移。
   • 固定第一个数 -1，双指针 left = 2，right = 5，求和 -1 + (-1) + 2 = 0，找到一个三元组 [-1, -1, 2]，同时跳过重复的 -1。
   • 固定第一个数 -1，双指针 left = 3，right = 4，求和 -1 + 0 + 1 = 0，找到一个三元组 [-1, 0, 1]，并跳过重复元素。
3. 返回结果：[[-1, -1, 2], [-1, 0, 1]]。

案例 2：输入 []

对于空数组，显然没有三元组存在，因此输出 []。

案例 3：输入 [0]

对于单元素数组，没有足够的元素来构成三元组，输出 []。

应用场景

三数之和问题不仅是一个经典的算法题，也有实际的应用场景。例如：

1. 金融分析：在金融领域，分析不同资产之间的组合可能性，或者寻找一些具有特定相对价格的三种资产。

2. 图形处理：在计算机图形学中，涉及到三维图形和多维数据处理时，三数之和的算法可以用来检测某些条件下的点集合，如三角形的面积、距离等。

3. 数据分析与聚类：在数据分析和机器学习领域，类似的三数之和问题可以用来检测数据中的某些特殊模式，尤其是在高维空间中的聚类和模式识别中。

总结

三数之和问题是一个非常经典的面试题，解决这一问题需要掌握排序和双指针等基础算法技巧。在实际应用中，这个问题不仅能够帮助我们理解数组操作，还能为我们在多个领域提供思路和方法。通过对该问题的解决方案进行优化和改进，我们可以提高代码的效率，减少不必要的计算，从而更好地应对各种规模的数据集。