我正在解决一个关于leetCode的练习，我提供了两个解决方案。练习是这样说的： 你会得到字符串 J 代表宝石的类型，S 代表你拥有的宝石。 S中的每个角色都是你拥有的一种石头。 你想知道你有多少石头也是珠宝。
J中的字母保证是不同的，J 和 S 中的所有字符都是字母。字母区分大小写，因此"a"被认为是与"A"不同类型的石头。 https://leetcode.com/problems/jewels-and-stones/
所以我给出了这两个解决方案：
const numJewelsInStones = function(J, S) {
let counter = 0;
let jArr = J.split('');
let sArr = S.split('');
for(let i = 0; i < jArr.length; i++) {
for(let j = 0; j < sArr.length; j++) {
if(jArr[i] === sArr[j]) {
counter++; }
}
}
return counter;
};'''
这个有两个不同的循环，应该是 O(n(：
const numJewelsInStones = function(J, S) {
let counter = 0;
let cache = {};
for(let i = 0; i < J.length; i++) {
cache[J[i]] = true;
}
for(let i = 0; i < S.length; i++) {
if(cache[S[i]]) {
console.log(S[i])
counter++
}
}
return counter;
}
根据leetCode，第一个解决方案需要44ms，第二个解决方案需要80ms。这怎么可能？
J 最多为 52 个字符(所有字母(。
所以我们处理的是小数字，而 O(( 表示法并没有那么有用...... O(s*j( <= O(52s(！
在第二种情况下，构建缓存的时间也不会保持一致，具体取决于它是否需要调整大小以及为什么假设查找是 O(n(？ 只是因为你的循环很简单并不意味着它调用的东西是。
但在任何情况下，运行时都将真正依赖于输入。
考虑到 s 可能比 j 大得多，并且您可以在打印后退出循环，我会重写。