10.4 哈希优化策略¶
在算法题中,我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。我们借助一个算法题来加深理解。
Question
给定一个整数数组 nums 和一个目标元素 target ,请在数组中搜索“和”为 target 的两个元素,并返回它们的数组索引。返回任意一个解即可。
10.4.1 线性查找:以时间换空间¶
考虑直接遍历所有可能的组合。如图 10-9 所示,我们开启一个两层循环,在每轮中判断两个整数的和是否为 target ,若是,则返回它们的索引。
图 10-9 线性查找求解两数之和
图解 10-9:暴力枚举求两数之和
用上三角表表示不同数组位置的所有配对。
给定整数数组 nums = [2, 7, 11, 15](索引从 0 到 3)与目标和 target = 13。
题目要求找出和为 target 的两个不同数组位置并返回它们的索引(同一个位置的元素不能重复使用两次)。暴力解法通过外层索引 i 与内层索引 j(j > i)开启两层循环,逐对检查两数之和。
画面下方的四行四列矩阵以行头和列头分别列出 2、7、11、15,仅在主对角线右上方的上三角区域填入六个候选和:既排除了主对角线上同一位置与自身相加的情况,也省去了左下角交换相加次序的重复配对。下表的元素和候选和来自图中矩阵;索引对由元素在输入中的位置按 0 起编号得到,配对算式由行列头组合。
矩阵中第 0 行(元素 2)与第 2 列(元素 11)交叉处的单元格 13 用紫蓝色文字标出。按照代码从左到右的枚举顺序,外层固定 i = 0(元素 2)后,内层先算 2 + 7 = 9,紧接着算到 2 + 11 = 13 即命中目标并直接返回 [0, 2];图中将其余候选和一并画出仅用于展示完整的组合空间,并不代表命中后仍需继续算完后续组合。
| 索引对 | 元素配对 | 和 |
|---|---|---|
| 0、1 | 2 + 7 | 9 |
| 0、2 | 2 + 11 | 13,命中目标 |
| 0、3 | 2 + 15 | 17 |
| 1、2 | 7 + 11 | 18 |
| 1、3 | 7 + 15 | 22 |
| 2、3 | 11 + 15 | 26 |
两层循环的时间复杂度为 O(n²),辅助空间为 O(1),体现以时间换空间。
代码如下所示:
/* 方法一:暴力枚举 */
int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) {
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
if (nums[i] + nums[j] == target) {
int *res = malloc(sizeof(int) * 2);
res[0] = i, res[1] = j;
*returnSize = 2;
return res;
}
}
}
*returnSize = 0;
return NULL;
}
可视化运行
此方法的时间复杂度为 \(O(n^2)\) ,空间复杂度为 \(O(1)\) ,在大数据量下非常耗时。
10.4.2 哈希查找:以空间换时间¶
考虑借助一个哈希表,键值对分别为数组元素和元素索引。循环遍历数组,每轮执行图 10-10 所示的步骤。
- 判断数字
target - nums[i]是否在哈希表中,若是,则直接返回这两个元素的索引。 - 将键值对
nums[i]和索引i添加进哈希表。
图 10-10 辅助哈希表求解两数之和
图解 10-10:哈希表求两数之和
用哈希表保存已见元素及索引,先查补数,再决定是否存入当前元素。
给定整数数组 nums = [2, 7, 11, 15](索引从 0 到 3)与目标和 target = 13。
借助辅助哈希表 map 记录已遍历过的元素:键(key,标有“元素”)存数组元素值,值(value,标有“索引”)存该元素对应的数组索引。单层循环每轮先查询补数 target − nums[i] 是否已在 map 中:若存在则立即返回 [map[target − nums[i]], i];若不存在才将当前键值对 nums[i]: i 写入 map。
每轮“先查补数、后存当前元素”的顺序保证了配对的另一个元素必定来自当前位置 i 之前的不同索引。三幅分步画面依次展示 i = 0、1、2 时的判断与哈希表状态(注意第 1 步画面展示的是完成首次插入 2: 0 之后的状态,而非空表)。
未找到补数 11,记录 2
i = 0 指向元素 2。图右侧说明:因为 13 − 2 = 11 不在初始空表中,所以写入 2: 0;当前 map = {2: 0}。尚未返回答案,下一项是索引 1 的 7。
未找到补数 6,记录 7
i = 1 指向元素 7。图右侧说明:因为 13 − 7 = 6 不在 map 中,所以写入 7: 1。此前表中只有键 2,写入后 map = {2: 0, 7: 1};尚未返回答案,下一项是索引 2 的 11。
找到补数 2,返回索引
i = 2 指向元素 11。图右侧说明:因为 13 − 11 = 2 已在 map 中,且 map[2] = 0,所以返回索引 [0, 2]。map 仍为 {2: 0, 7: 1};11 不再入表,索引 3 的 15 不再处理。
在哈希查询平均为 O(1) 的前提下,总体平均时间为 O(n),辅助空间为 O(n),体现以空间换时间。
实现代码如下所示,仅需单层循环即可:
/* 方法二:辅助哈希表 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
int size = nums.size();
// 辅助哈希表,空间复杂度为 O(n)
unordered_map<int, int> dic;
// 单层循环,时间复杂度为 O(n)
for (int i = 0; i < size; i++) {
if (dic.find(target - nums[i]) != dic.end()) {
return {dic[target - nums[i]], i};
}
dic.emplace(nums[i], i);
}
return {};
}
/* 方法二:辅助哈希表 */
int[] twoSumHashTable(int[] nums, int target) {
int size = nums.length;
// 辅助哈希表,空间复杂度为 O(n)
Map<Integer, Integer> dic = new HashMap<>();
// 单层循环,时间复杂度为 O(n)
for (int i = 0; i < size; i++) {
if (dic.containsKey(target - nums[i])) {
return new int[] { dic.get(target - nums[i]), i };
}
dic.put(nums[i], i);
}
return new int[0];
}
/* 方法二:辅助哈希表 */
int[] TwoSumHashTable(int[] nums, int target) {
int size = nums.Length;
// 辅助哈希表,空间复杂度为 O(n)
Dictionary<int, int> dic = [];
// 单层循环,时间复杂度为 O(n)
for (int i = 0; i < size; i++) {
if (dic.ContainsKey(target - nums[i])) {
return [dic[target - nums[i]], i];
}
dic.Add(nums[i], i);
}
return [];
}
/* 方法二:辅助哈希表 */
function twoSumHashTable(nums: number[], target: number): number[] {
// 辅助哈希表,空间复杂度为 O(n)
let m: Map<number, number> = new Map();
// 单层循环,时间复杂度为 O(n)
for (let i = 0; i < nums.length; i++) {
let index = m.get(target - nums[i]);
if (index !== undefined) {
return [index, i];
} else {
m.set(nums[i], i);
}
}
return [];
}
/* 方法二: 辅助哈希表 */
List<int> twoSumHashTable(List<int> nums, int target) {
int size = nums.length;
// 辅助哈希表,空间复杂度为 O(n)
Map<int, int> dic = HashMap();
// 单层循环,时间复杂度为 O(n)
for (var i = 0; i < size; i++) {
if (dic.containsKey(target - nums[i])) {
return [dic[target - nums[i]]!, i];
}
dic.putIfAbsent(nums[i], () => i);
}
return [0];
}
/* 方法二:辅助哈希表 */
pub fn two_sum_hash_table(nums: &Vec<i32>, target: i32) -> Option<Vec<i32>> {
// 辅助哈希表,空间复杂度为 O(n)
let mut dic = HashMap::new();
// 单层循环,时间复杂度为 O(n)
for (i, num) in nums.iter().enumerate() {
match dic.get(&(target - num)) {
Some(v) => return Some(vec![*v as i32, i as i32]),
None => dic.insert(num, i as i32),
};
}
None
}
/* 哈希表 */
typedef struct {
int key;
int val;
UT_hash_handle hh; // 基于 uthash.h 实现
} HashTable;
/* 哈希表查询 */
HashTable *find(HashTable *h, int key) {
HashTable *tmp;
HASH_FIND_INT(h, &key, tmp);
return tmp;
}
/* 哈希表元素插入 */
void insert(HashTable **h, int key, int val) {
HashTable *t = find(*h, key);
if (t == NULL) {
HashTable *tmp = malloc(sizeof(HashTable));
tmp->key = key, tmp->val = val;
HASH_ADD_INT(*h, key, tmp);
} else {
t->val = val;
}
}
/* 方法二:辅助哈希表 */
int *twoSumHashTable(int *nums, int numsSize, int target, int *returnSize) {
HashTable *hashtable = NULL;
for (int i = 0; i < numsSize; i++) {
HashTable *t = find(hashtable, target - nums[i]);
if (t != NULL) {
int *res = malloc(sizeof(int) * 2);
res[0] = t->val, res[1] = i;
*returnSize = 2;
return res;
}
insert(&hashtable, nums[i], i);
}
*returnSize = 0;
return NULL;
}
/* 方法二:辅助哈希表 */
fun twoSumHashTable(nums: IntArray, target: Int): IntArray {
val size = nums.size
// 辅助哈希表,空间复杂度为 O(n)
val dic = HashMap<Int, Int>()
// 单层循环,时间复杂度为 O(n)
for (i in 0..<size) {
if (dic.containsKey(target - nums[i])) {
return intArrayOf(dic[target - nums[i]]!!, i)
}
dic[nums[i]] = i
}
return IntArray(0)
}
可视化运行
此方法通过哈希查找将时间复杂度从 \(O(n^2)\) 降至 \(O(n)\) ,大幅提升运行效率。
由于需要维护一个额外的哈希表,因此空间复杂度为 \(O(n)\) 。尽管如此,该方法的整体时空效率更为均衡,因此它是本题的最优解法。