解法一：暴力法

算法

暴力法非常直接。遍历每个元素 ，并查找是否存在一个值与 相等的目标元素。

复杂度分析

• 时间复杂度：。对于每个元素，我们试图通过遍历数组的其余部分来寻找它的补数，这需要 时间。因此总时间复杂度为 。
• 空间复杂度：。所需空间不依赖于输入数组的大小，因此只使用了常数空间。

解法二：两遍哈希表

思路

为了优化时间复杂度，我们需要一种更高效的方法来检查数组中是否存在补数。如果补数存在，我们需要得到它的索引。将数组中的每个元素映射到其索引的最佳方法是什么？答案是哈希表。

我们可以通过用空间换时间的方式，将查找时间从 降低到 。哈希表非常适合这个目的，因为它支持在接近常数时间内进行快速查找。之所以说“接近”，是因为如果发生哈希冲突，查找可能会退化到 的时间。但是，只要哈希函数选择得当，哈希表的查找时间可以平摊为 。

算法

一个简单的实现使用两次迭代。在第一次迭代中，我们将每个元素的值作为键，将其索引作为值添加到哈希表中。然后，在第二次迭代中，我们检查每个元素的补数（）是否存在于哈希表中。如果存在，我们返回当前元素的索引和其补数的索引。需要注意的是，补数不能是 本身！

复杂度分析

• 时间复杂度：。我们恰好遍历了包含 个元素的列表两次。由于哈希表将查找时间降低到 ，总时间复杂度为 。
• 空间复杂度：。所需的额外空间取决于哈希表中存储的元素数量，该表存储了 个元素。

解法三：一遍哈希表

算法

事实证明，我们可以一次完成。在遍历并将元素插入哈希表的同时，我们也会回顾并检查当前元素的补数是否已经存在于哈希表中。如果存在，我们就找到了一个解，并立即返回两个索引。

复杂度分析

• 时间复杂度：。我们只遍历了包含 个元素的列表一次。哈希表中的每次查找仅需 时间。
• 空间复杂度：。所需的额外空间取决于哈希表中存储的元素数量，该表最多存储 个元素。