java - for 循环与 if-else 语句中的代码

Question

我试图解决这个问题:https://leetcode.com/problems/longest-substring-without-repeating-characters/

以下代码在 44 毫秒内通过了所有测试。

    for (int i = 0; i < s.length(); i++){
        if (!mp.containsKey(s.charAt(i))){
            mp.put(s.charAt(i), i);
            //max = Math.max(max, i-first+1);
        }
        else {
            if (mp.get(s.charAt(i))+1>=first){
                first = mp.get(s.charAt(i))+1;
            }
            mp.put(s.charAt(i), i);
            //max = Math.max(max, i-first+1);
        }
        max = Math.max(max, i-first+1);
    }

但下面的代码只用了 20 毫秒就通过了所有测试。

    for (int i = 0; i < s.length(); i++){
        if (!mp.containsKey(s.charAt(i))){
            mp.put(s.charAt(i), i);
            max = Math.max(max, i-first+1);
        }
        else {
            if (mp.get(s.charAt(i))+1>=first){
                first = mp.get(s.charAt(i))+1;
            }
            mp.put(s.charAt(i), i);
            max = Math.max(max, i-first+1);
        }
    }

为什么会有如此显着的差异？最大值在两个示例中只更改一次，但在 if-else 语句中更改它比在 for 循环结束时更改它更有效。这是一个异常(exception)还是我们应该在编码时遵循这个标准？

Answer 1

关于简化(不是早期优化，见最大值!)一个人得到

for (int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);
    Integer n = mp.get(ch):
    if (n != null) {
        first = Math.max(first, n + 1);
    }
    mp.put(ch, i);
    max = Math.max(max, i - first + 1);
}

注意原始版本中值 i 的双重放置。如果将第一个 Math.max 替换为 if，代码可能会更快。

很难就此发表声明。为了加快两个原始版本的速度，也许热点编译器看到了冗余。或其他。

很高兴看到一个 java 8 版本，使用 mp.putIfAbsent 或类似的，但这可能会使速度变慢。