第十六章 面试题：三数之和

在算法面试中，数组相关的题目占据了相当大的比重，它们不仅考察了候选人对数据结构的理解，还检验了解决问题的逻辑思维能力和编程技巧。其中，“三数之和”是一道经典的题目，它要求在给定的一个整数数组中找到所有独特的三元组，使得这三个数之和为零。这个问题看似简单，实则蕴含了多种优化思路，是评估算法设计能力的好题。

1. 问题描述

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

注意：

• 答案中不可以包含重复的三元组。
• 数组中的元素可能包含重复值。

2. 解题思路

要解决这个问题，最直接的方法是三层嵌套循环遍历数组，检查所有可能的三元组是否满足条件。然而，这种方法的时间复杂度为 O(n^3)，在数组较大时效率极低，难以通过面试。因此，我们需要寻找更高效的算法。

一个优化的思路是，首先对数组进行排序，然后利用排序后的数组特性来减少不必要的遍历。排序后，我们可以通过固定一个元素，然后使用双指针技术来寻找另外两个元素，从而将问题转化为一个两数之和的问题，其时间复杂度可以降低到 O(n^2)。

3. 排序与双指针法

步骤一：排序

首先对数组进行排序，排序的时间复杂度为 O(n log n)。

步骤二：固定一个元素，双指针查找

• 遍历数组 nums，将当前元素记为 nums[i]，作为三元组中的第一个数。
• 使用两个指针 left 和 right，分别指向 i+1 和数组末尾 n-1。
• 进入循环，判断 nums[i] + nums[left] + nums[right] 的值：
  • 如果和为 0，则找到了一个满足条件的三元组，将其加入结果集，并移动 left 和 right 指针（注意跳过重复元素，以避免重复的三元组）。
  • 如果和小于 0，说明需要增大和，因此将 left 指针右移。
  • 如果和大于 0，说明需要减小和，因此将 right 指针左移。
• 当 left 大于等于 right 时，退出内层循环，继续遍历数组中的下一个元素。

4. 代码实现

以下是该算法的 Python 实现：

def threeSum(nums):
    nums.sort()  # 先对数组进行排序
    result = []
    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:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.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
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result
# 示例
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))
# 输出: [[-1, -1, 2], [-1, 0, 1]]

5. 复杂度分析

• 时间复杂度：排序的时间复杂度为 O(n log n)，遍历数组和双指针查找的总时间复杂度为 O(n^2)（因为对每个元素，双指针最多遍历整个数组一次）。所以总时间复杂度为 O(n^2)。
• 空间复杂度：主要空间消耗在排序上，如果采用原地排序算法（如快速排序、堆排序等），则空间复杂度为 O(log n)（递归栈空间）或 O(1)（非递归实现）。结果集的空间复杂度取决于满足条件的三元组数量，最坏情况下为 O(n^2)，但通常远小于此。

6. 面试技巧与扩展

• 面试技巧：在面试中，除了给出正确的解法外，还应主动提及算法的时间复杂度和空间复杂度，并讨论可能的优化点。例如，可以提到如何避免重复的三元组，以及为什么选择排序和双指针的方法。
• 问题扩展：可以将此问题扩展为“四数之和”、“两数之和的目标值不为零”等，考察候选人的问题解决能力和算法迁移能力。
• 边界情况：注意处理空数组、数组只有一个元素等边界情况，确保代码的健壮性。

通过“三数之和”这道面试题，我们不仅可以锻炼数组和排序相关的知识，还能深入理解双指针技术的应用，以及如何通过优化算法来减少不必要的计算，提升程序的执行效率。希望本章内容能帮助你在算法面试中更加游刃有余。