3. 无重复字符的最长子串 3. Longest Substring Without Repeating Characters

[Shellbye]

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

初始思路

这个题目虽然标注为“简单”，但是我也依然是断断续续利用业余时间做了两三天才通过。看到这个题的第一反应就是用双指针，一个 fast 一个 slow，最后计算两者的差值来求最大值。这可能也是因为我前不久做了好几个链表的题目，其中检测是否有环等题目都是用双指针完成的，所以就“拿着锤子，看什么都是钉子”了。

我的第一反应是 fast 指针一个一个的扫描，然后和slow 指针的值比较，发现重复的，就 slow 指针往前一位。但是实际实现的时候，发现是不对的，因为重复的字符不一定是刚好在 slow 所指向的位置，而是可能是中间某一个位置，比如 abcdefcd，当已扫描字符串为 abcdef 且当前正在扫描的是 c 的时候，按照这个错误的思路，a != c 我们认为还没有重复，但是 c 和第三个位置的 c 已经重复了！

于是为了修正这个问题，我需要一个集合，记录了已经存在的字符，光有 fast 和 slow 是不够的。顺着这个思路，当发现某个字符（上例中的 c ）已经存在与集合中时，我们就知道该更新一下当前的最长子串的长度了，因为再往前就要移除一些重复的字符了。那么这个时候问题来了，要从已扫描的字符串（上例中的 abcdef）中移除多少个头部字符呢？我们需要从头部开始找，一直到找到重复的字符的位置，然后从这个位置开始，它前面的都不用，它后面的重新构建新的集合。构建好新的集合之后，我们继续扫描，于是就有如下勉强通过的代码了（i 其实就是 fast）：

    public int lengthOfLongestSubstring(String s) {
//        System.out.println(String.format("s.length(): %s", s.length()));
        if (s == null) {
            return 0;
        }
        if (s.length() <= 1) {
            return s.length();
        }
        int slow = 0;
        int maxL = 0;
        Set<Character> existChars = new HashSet<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
//            System.out.println(String.format("process i: %s, char: %s", i, c));
            if (existChars.contains(c)) {
                existChars = new HashSet<>();
                // 出现重复，需要更新 slow 的位置，更新 maxL, 更新 existChars
                if (i - slow > maxL) {
                    maxL = i - slow;
                }
                boolean reput = false;
                for (int j = slow; j <= i; j++) {
                    // 更新 existChars
                    if (reput) {
                        existChars.add(s.charAt(j));
                    }
                    if (!reput && s.charAt(j) == c) {
                        // j 就是重复的位置
                        slow = j + 1;
                        reput = true;
                    }
                }
            } else {
                existChars.add(c);
            }
        }
        // 最后一次计算
        if (s.length() - slow > maxL) {
            maxL = s.length() - slow;
        }
        return maxL;
    }

升级版本

在看了官方的解题思路之后，才意识到，以上解法中，其实有一些步骤是可以进一步优化的。比如每次遇到重复的字符之后，我就清空了已经存在的字符集合，然后在依次判断是否重复，重新装回集合。其实这个是有点多费手续了，仔细想想，其实我就是想把重复的丢掉而已，没必要整体清空，一个一个的去重重复的就可以：

    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        if (s.length() <= 1) {
            return s.length();
        }
        int slow = 0;
        int fast = 0;
        int maxL = 0;
        Set<Character> existChars = new HashSet<>();
        while(slow < s.length() && fast < s.length()) {
            char c = s.charAt(fast);
            if (existChars.contains(c)) {
                existChars.remove(s.charAt(slow));
                maxL = Math.max(maxL, fast - slow);
                slow++;
            } else {
                existChars.add(c);
                fast++;
            }
        }
        maxL = Math.max(maxL, fast - slow);
        return maxL;
    }

进一步优化

以上的升级版本还有一个地方可以优化，就是每次遇到有重复字符出现时，都要一个一个的剔除重复的，如果我们在记录字符的同时记录了字符的位置，那么 slow 就可以之下指向最终应该到的位置，而不用一步一步的过去：

    public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        if (s.length() <= 1) {
            return s.length();
        }
        int slow = 0;
        int fast = 0;
        int maxL = 0;
        Map<Character, Integer> existCharLocationMap = new HashMap<>();
        while(slow < s.length() && fast < s.length()) {
            char c = s.charAt(fast);
            if (existCharLocationMap.keySet().contains(c) && existCharLocationMap.get(c) >= slow) {
                maxL = Math.max(maxL, fast - slow);
                slow = existCharLocationMap.get(c) + 1;
                existCharLocationMap.remove(c);
            } else {
                existCharLocationMap.put(c, fast);
                fast++;
            }
        }
        maxL = Math.max(maxL, fast - slow);
        return maxL;
    }

其实就是滑动窗口

上面的两种解法，就是处理字符串问题常用的滑动窗口方法，前一个是尾部一次一格的滑动窗口，后一个是一次一步到位的。

[SuZhenYu2]

假设都是小写字母 可以创建一个数组 int[] cs =new int[26]; char[] ss = s.toCharArray(); int count=0; for(int i=0;i<ss.length;i++){ if(cs[ss[i]-'a'] ==0){ cs[ss[i]-'a'] =1; count++; } } return count;