LeetCode-Longest Substring Without Repeating Characters

没想到这道题居然拖了两天才写完。首先要理解题意，题目是让寻找最长无重复的串，而非最长重复的模式，最开始在这里绕了一些弯儿。

下面是最直接的方法，就是用一个窗口（start，length）标识当前串，然后一个一个字母往前走，如果遇到有重复的，向前走一个，所以大概复杂度是平方，运行时间也不是很乐观，基本垫底。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] sc=s.toCharArray();
        if(sc.length==0)
            return 0;
        int start=0;
        int len=1;
        int longest=1;
        boolean needPlus;
        while(start+len<sc.length){
            char nowChar=sc[start+len];
            needPlus=true;
            for(int j=start;j<start+len;j++){
                if(sc[j]==nowChar){
                    start=j+1;
                    longest=len>longest?len:longest;
                    len=1;
                    needPlus=false;
                    break;
                }
            }
            if(needPlus){
                len++;
                longest=len>longest?len:longest;
            }
        }
        return longest;
    }
}

看了一下 Solution，发现他们把上面答案里的第二层循环使用 Java 的 HashSet 代替，感觉可以提高效率。但是发现这种方法并没有提高太多效率，甚至在处理 start 位置的问题上还没有滑动窗口灵活,每次只能向前一个。用他的思路改写一下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] sc=s.toCharArray();
        int start=0;
        int len=0;
        int longest=0;
        Set<Character> charSet=new HashSet<>();
        while(start+len<sc.length){
            char nowChar=sc[start+len];
            if(!charSet.contains(nowChar)){
                charSet.add(nowChar);
                longest=++len>longest?len:longest;
            }else{
                charSet.remove(sc[start++]);
                if(len>0) len--;
            }
            // System.out.println("start "+start);
            // System.out.println("len "+len);
        }
        return longest;
    }
}

后面的方法呼之欲出，用 HashMap 记录位置，然后沿用滑动窗口的方案，效率可以进一步提升。（用 start 和 length 做窗口，bug 会有一些 bug，懒得调了，直接用官方例子吧）

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

最最后就是假设只有 ascii 码的话，使用 char[128]代替 HashMap，速度进一步提升。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}