快速寻找满足条件的两个数

Question

编程之美题目2.12:

给定一个数组,如何找出数组中的两个数字,让这两个数字之和等于一个给定的值.

书上有一个解法是使用哈希表,不明白怎么使用?求高手可以具体解释一下.

Answer 1

考虑最简单的情况，数组中的数均不相同。首先建哈希表，对每个元素 hash_table[hash(element)] = 1。

假定和为s，遍历数组中的元素t,若hash_table[hash(s-t)]==1(说明s-t在数组中)，则数组中的t, s-t满足条件。

时间复杂度是线性的。