3. 无重复字符的最长子串-java实现

第三题：无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

V1版本

最开始想到的就是通过双重for循环依次去匹配，获取最大长度，但想了想这种方式肯定是效率最差的，
于是乎想着用散列表来保存节点出现的位置，然后在去计算最大长度，结果在和种测试用例面前缝缝补补，代码又臭又长，只好先放弃了，先用最暴力的方法解决一下吧，代码如下

public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        // 用于校验是否遇到重复值
        Set<Character> set;
        // 定义最大长度
        int maxLength = 0;
        for (int i = 0; i < chars.length; i++) {
            // 剩下的总长度比当前获取的最大长度小，则没必要在执行下去了
            if (s.length() - 1 < maxLength) {
                return maxLength;
            }
            set = new HashSet<>();
            int j = i;
            for (; j < s.length(); j++) {
                if (!set.add(chars[j])) {
                    maxLength = Math.max(maxLength, j - i);
                    break;
                }
            }
            // 没有遇到重复字条跳出的情况
            if (j >= s.length()) {
                maxLength = Math.max(maxLength, s.length() - i);
            }
        }
        return maxLength;
    }

结果也是不出所料，效率太低，继续优化吧

image.png

V2版本

有了V1暴力破解的经验，V1效率太低的原因就是重复的操作太多了，得想办法减少这种不必要的重复工作
想想其实没必要每次都从头开始匹配
例：abcabcbb
第一次匹配到abc 第四个字符了a,重复了，我可以记录一下这时的最大长方度，然后将a去掉，继续用bca往下匹配
这样只需要循环一遍即可得到结果，说干就干，代码如下,利用了队列来保存有效不得复的字符

public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        // 用于校验是否遇到重复值
        Set<Character> set = new HashSet<>();
        // 队列保存走过的字符
        Queue<Character> queue = new LinkedBlockingDeque<>();
        // 定义最大长度
        int maxLength = 0;
        // 当前字符
        char curChar;
        // 被队列弹出的字符
        char pollChar;
        for (int i = 0; i < chars.length; i++) {
            // 在队列中添加一个元素
            curChar = chars[i];
            queue.add(curChar);
            // 添加到set中，校验是否有重复
            if (set.add(curChar)) {
                continue;
            }
            // 有重复字符了，获取当前最在不重复字符长度，由于queue里面有一个重复的字符，计算的时候需要减1
            maxLength = Math.max(maxLength, queue.size() - 1);
            // 此时需要弹出与队列中与当前字符相同的字符之前的所有字符，包括当前字符
            do {
                // 弹出并删除头字符
                pollChar = queue.poll();
                // 头字符和当前字符不一样，将该头符在set集合中删除，并继续执行弹出操作
                if (curChar != pollChar) {
                    set.remove(pollChar);
                }
            } while (curChar != pollChar);
        }
        // 有可能存在aab这种没有收尾的情况
        return Math.max(maxLength, queue.size());
    }

可是执行效率依旧感人，我得去找找大佬们的思路了

image.png

V3版本

参考官方版本，官方版本用的是滑动窗口，简洁太多，根本不需要另外用队列来记录字符
一个map就搞定了，节约不少空间和时间成本，又强又骚，向大牛学习

public int lengthOfLongestSubstring(String s) {
        // 定义一个map保存字符与坐标信息
        Map<Character, Integer> map = new HashMap<>();
        // 最大长度
        int maxLength = 0;
        int num = s.length();
        int start = -1, end = 0;

        // 当前字符
        char curChar;
        for (; end < num; end++) {
            curChar = s.charAt(end);
            // 校验字符在map中是否存在
            if (map.containsKey(curChar)) {
                // 已存在，则需要将start向后滑动
                start = Math.max(map.get(curChar), start);
            }
            maxLength = Math.max(maxLength, end - start);
            map.put(curChar, end);
        }
        return maxLength;
    }

image.png