16 | 面试题：三数之和-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

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

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

#### 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 实现：

```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. 面试技巧与扩展

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

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

该分类下的相关小册推荐：

编程之道-算法面试(上)

编程之道-算法面试(下)

数据结构与算法(中)

数据结构与算法之美

业务开发实用算法精讲

数据结构与算法(上)

数据结构与算法(下)