为什么此O（n ^ 2）代码比O（n）执行得更快？

Question

我编写了两种方法的代码，以找出LeetCode字符串中的第一个唯一字符。

问题陈述： 给定一个字符串，找到其中的第一个非重复字符并返回其索引。如果不存在，则返回-1。

示例测试用例：

s =“ leetcode”返回0。

s =“ loveleetcode”，返回2。

方法1（O（n））（如果我错了，请纠正我）：

class Solution {
    public int firstUniqChar(String s) {

        HashMap<Character,Integer> charHash = new HashMap<>();

        int res = -1;

        for (int i = 0; i < s.length(); i++) {

            Integer count = charHash.get(s.charAt(i));

            if (count == null){
                charHash.put(s.charAt(i),1);
            }
            else {
                charHash.put(s.charAt(i),count + 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {

            if (charHash.get(s.charAt(i)) == 1) {
                res = i;
                break;
            }
        }

        return res;
    }
}

方法2（O（n ^ 2））：

class Solution {
    public int firstUniqChar(String s) {

        char[] a = s.toCharArray();
        int res = -1;

        for(int i=0; i<a.length;i++){
            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
                res = i;
                break;
            }
        }
        return res;
    }
}

在方法2中，我认为复杂度应为O（n ^ 2），因为indexOf在此处以O（n * 1）执行。

但是，当我在LeetCode上执行这两个解决方案时，方法2的运行时间为19毫秒，方法1的运行时间为92毫秒。为什么会这样？

我假设LeetCode对最佳，最差和平均情况下的小和大输入值进行测试。

更新：

我知道以下事实：对于某些n <n1，O（n ^ 2算法）的性能更好。在这个问题中，我想了解为什么在这种情况下会发生这种情况。即方法1的哪一部分使其变慢。

LeetCode链接到问题

Answer 1

对于非常短字符串如单角色作成的成本HashMap，重新调整其大小，查找条目，而装箱和拆箱的char成Character威力遮荫的成本String.indexOf()，这可能是考虑热和JVM无论哪种方式，内联。

另一个原因可能是RAM访问的成本。随着更多的HashMap，Character并Integer参与查找的对象可能有必要对从RAM额外的访问。单次访问时间约为100
ns，这可能会加起来。

看看 Bjarne Stroustrup：为什么要避免使用链表 。本讲座说明了性能与复杂性并不相同，内存访问可能成为算法的杀手er。