algorithm medium

    3. 无重复字符的最长子串

    思路一

    我最先想到的是用递归, 核心思想是, 遇到重复的字符, 则将字符串分开, 再递归计算前面的重复位置的下一位开始的字符串的最大值, 最后再比较得到最大值. 代码如下:

    1.     public static int lengthOfLongestSubstring1(String s) {
    2.         int length = s.length();
    3.         if (length <= 1) {return length;}
    4.         int count = 0;
    5.         int maxs = 0;
    6.         Integer p;
    7.         HashMap<Character, Integer> map = new HashMap<>();
    8.         for ( int i = 0; i < length; i++) {
    9.             if((p = map.put(s.charAt(i), i)) == null) {
    10.                 count++;
    11.             } else {
    12.                 maxs = lengthOfLongestSubstring1(s.substring(p + 1));
    13.                 break;
    14.             }
    15.         }
    16.         return count > maxs ? count : maxs;
    17.     }

    效率

    • 执行用时 : 159 ms, 在所有 Java 提交中击败了 10.20% 的用户
    • 内存消耗 : 47.9 MB, 在所有 Java 提交中击败了5.20% 的用户

    可以看出效率并不高.

    思路二 滑动窗口

    public static int lengthOfLongestSubstring2(String s) {
    if (s.length() == 0 ){
        return 0;
    }
    char[] windows = new char[128];   //用于记录每个字符
    int left = 0 , right = 0 ;        //双指针控制窗口大小
    int maxlength = 0 ;               //记录窗口最大长度

    while(right< s.length()){
        char ch = s.charAt(right);
        windows[ch]++; 
        // abcdefcg
        //   l   r
        // 如果有重复字符则左边窗口一直加，直到剔除重复字符, 相当于滑动清除到重复字符前位的这个过程
        while (windows[ch] > 1){
            char ch1 = s.charAt(left);
            windows[ch1]--;
            left++;
        }
        maxlength = Math.max(right - left+1 , maxlength);
        right++;
    }
    return maxlength;
    }
}

    这个问题其实可以算是滑动窗口问题, 那么最好使用 left 和 right 双指针.

    这里另一个关键是使用了字符表, 也就是默认只有数字和字母等 ascii 表码, 对于所有字符要用 new char[65535], 这样空间效率低. 这个用法在计算字符串中所有字符出现的次数使使用过.

    最后, “如果有重复字符则左边窗口一直加，直到剔除重复字符, 相当于滑动清除到重复字符前位的这个过程”这个过程也是关键, 这个和我自己的想法是一样的, 只是实现方式不同, 这里要简洁很多, 另一个原因是使用了数组码表.