Leetcode 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

原题链接：Longest Substring Without Repeating Characters

　　此题题意是找出一个不包含相同字母的最长子串，题目给出了两个例子来说明题意，但这两个例子具有误导性，让你误以为字符串中只有小写字母。还好我是心机boy，我把大写字母的情况也给考虑进去了，不过。。。。字符串里竟然有特殊字符，于是贡献了一次wrong answer，这次我把ascii字符表都考虑进去，然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围，面试中可以和面试官去确认数据范围，也能显得你比较严谨。

　　这题也有笨方法解的，就是枚举所有子串，然后再判断其中是否包含相同字符，假设字符串长度是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));
    }
}

~谢谢打赏~

赏