使用哈希表(Hash Table)或映射(Map)解决。
示例:
假设我们有两个数组a和b,现在要找到a中所有出现在b中的元素。
不好的解决方案:
使用双层循环来查找:
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < b.length; j++) {
if (a[i] === b[j]) {
console.log(a[i]);
}
}
}
这样做的问题在于,如果a和b的长度都很大,那么会导致非常低效的嵌套迭代。
好的解决方案:
我们可以使用哈希表(Hash Table)或映射(Map)来解决这个问题。我们可以先遍历b数组,将其中的元素作为哈希表的键,而值则并不重要。然后再遍历a数组,对于每一个元素,我们只需要查看是否在哈希表中存在对应的键即可。
代码示例:
function findCommonElements(a, b) {
const hash = new Map();
const result = [];
// 遍历 b 数组,把每个元素当做键存入哈希表
for (let i = 0; i < b.length; i++) {
hash.set(b[i], true);
}
// 遍历 a 数组,查看哈希表中是否存在对应的键
for (let i = 0; i < a.length; i++) {
if (hash.get(a[i])) {
result.push(a[i]);
}
}
return result;
}
这个解决方案的时间复杂度为O(m + n),其中m为a数组的长度,n为b数组的长度,比起嵌套循环的O