最近在leetcode上看到一个题目
https://leetcode.com/problems/longest-substring-without-repeating-characters/
难度平平
但是自己写的代码总是被一个测试用例判定超时
也就是时间复杂度超过要求了
我的实现如下

    public int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) return 0;
        if (s.length() == 1) return 1;
        int result = 0;
        Set<Character> temp = new HashSet<Character>();
        int p = 0;
        int start = 0;
        while (p < s.length()) {
            char curChar = s.charAt(p);
            if (!temp.contains(curChar)) {
                temp.add(curChar);
            } else {
                // mark the longest sub string length
                result = Math.max(result, p - start + 1);

                // remove the duplicated char and chars before the duplicated char
                while (s.charAt(start) != curChar) {
                    temp.remove(s.charAt(start));
                    start++;
                }

                // reset start and add curChar into map
                start = start + 1;
            }
            p++;
        }
        result = Math.max(result, p - start + 1);
        return result;
    }

别人写的就跑的过去
链接如下
https://leetcode.com/discuss/60454/simple-ac-o-n-java-solution
代码如下

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        Set<Character> set = new HashSet<Character>();
        int start = 0;
        int end = 0;
        int res = 1;
        set.add(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
            } else {
                res = Math.max(res, end - start + 1);
                while (s.charAt(start) != c) {
                    set.remove(s.charAt(start));
                    start++;
                }
                start++;
            }
            end = i;
        }
        res = Math.max(res, end - start + 1);
        return res;
    }

可以看出仅仅是循环的方式不同

我在外层用了while
他在外层用了for
结果他比我快

我天真的以为for天然快？
然后改为外层for内层for的循环
结果还是比外层for内层while要慢

求解答

附上那个比较长的测试用例

"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~
......上面这一组字符重复100遍
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCD"