javascript - String.prototype.indexOf() 的运行时复杂度是多少？

Question

在 Leetcode 上解决 387. First Unique Character in a String 时，我对indexOf().

我最初使用 2 循环方法解决了这个问题，如下所示：

var firstUniqChar = function(s) {
    const map = new Map();
    const arr = s.split('');
    let answer = -1;
    
    for (let i = 0; i < arr.length; i++) {
        if (map.has(arr[i])) {
            map.set(arr[i], -1);
        } else {
            map.set(arr[i], i);
        }
    }
    map.forEach((value) => {
      if (value !== -1) {
                if (value < answer || answer === -1) {
            answer = value;
        }
      }
    });
    
    return answer;
};

它的运行时间为 100 毫秒，比其他 JS 提交快 91.92%。当我查看第 99 个百分位数的答案时，它是一个单循环解决方案，.indexOf()每个字符使用两次。

var firstUniqChar = function(s) {
    for (let i = 0; i < s.length; i++){
        if (s.indexOf(s[i], i+1) === -1 && 
            s.indexOf(s[i]) === i) {
            return i;   
        }
    }
    return -1
};

参考Java 中的一个类似问题，它的indexOf()函数似乎使用了一种简单的字符串搜索算法，运行时复杂度为O(n + m)or O(n*m)。如果是这种情况，那么第一个解决方案应该更快。但是，提交第二个解决方案给了我 88 毫秒（98.52 个百分点）。

我很难理解背后是如何indexOf()发生的，这会给第二种解决方案带来线性运行时复杂性。JavaScript 中是否indexOf()使用了不同的算法，使其运行时间为O(1)? 如果有人能对此有所了解，将不胜感激。

标签： javascriptstringalgorithmsearch