Leetcode 3. Longest Substring Without Repeating Characters

　　这题也有笨方法解的，就是枚举所有子串，然后再判断其中是否包含相同字符，假设字符串长度是n，很明显枚举的时间复杂度是O(n^2)。如果你真在面试中遇到了此题，暴力枚举的方法绝对不会是正确答案，所以我们还需要深入思考下。 实话告诉你，我这里有O(n)的解法。

　　如果字符串中仅限小写字母，很显然，任何情况下这个包含不重复字符的子串最长不会超过26，我就不信你不知道为啥。 首先个小技巧，如果最快的判断一个字符是否在字符串中存在过了——当然是用一个数组记录下这个字符出现的次数，而不是遍历一遍字符串，我代码中cnt数组就是来做这事的。 我用两个变量 start和end来表示子串的起始和末尾位置，cnt数组来表示start和end之间各个字符有多少个。
　　最重要的地方来了，当我遍历到原字符某个位置（我表示为end）的时候，如果end位置的字符（str[end]）在cnt数组中为0，那么意味着我把str[end]加入子串中(也就是cnt[str[end]]++)，该子串依旧是不包含重复字符的。 相反，如果start到end-1之间的子串已经包含字符str[end]的时候，我就把start的位置往后挪(start++)，直到start到end-1表示的子串不包含str[end]这个字符。 我只需要一直保证start到end之间不包含重复字符就好了，然后取最大的end-start就是我们需要的答案了。
　　以下就是我的解题代码，击败了85.63%的java代码，别看有三个while，两层的while循环，时间复杂度确确实实只有O(n)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (null == s)
            return 0;
        int len = s.length();
        int start = 0, end = 0;
        int[] cnt = new int[130];
        int ans = 0;
        while (end < len) {
            while (cnt[s.charAt(end)] > 0 && start < len) {
                cnt[s.charAt(start)]--;
                start++;
            }
            while (end < len && cnt[s.charAt(end)] == 0) {
                cnt[s.charAt(end)]++;
                end++;
            }
            if (end - start > ans)
                ans = end - start;
        }
        return ans;
    }
    public static void main(String[] args) {
        String str = "p$%^&*(*&^%$#$%^&*(";
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring(str));
    }
}