【力扣算法日记】无重复字符的最长子串

最近刷了很多算法题,这些解题过程也拓展了自己的思路,是个适合记录的素材。所以决定在继技术知识点详解的【一文系列】之后,开启新坑——【力扣算法系列】,来记录力扣刷题过程。

分享题目不确定,目前打算只分享我认为值得分享的题目,或者你们有什么想要我分享的题目,我愿意去研究透彻之后出分析详解!分享的过程也是自我学习的过程!

leetCode

那么今天,我们分享第一道题目:无重复字符的最长子串

题目

无重复字符的最长子串

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

来源:https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:

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

提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成


解题

暴力法

这是最容易想到的方法,当然也是最废的方法。不过我们在解题的时候,可以先尝试暴力解法,然后再一步步着手优化,或想出更好的方法,这也是一种解题思路。在这道题目中,暴力解法就是逐个检查所有的子字符串,看它是否不含有重复的字符。

public static int lengthOfLongestSubstring(String s) {
    char[] chars = s.toCharArray();
    Map<Character, Integer> subChars = new HashMap<Character, Integer>(chars.length);
    int maxSize = 0;
    int repeatIndex = -1;
    int i = 0;
    while (i < chars.length) {
        for (int j = i; j < chars.length; j++) {
            char c = chars[j];
            if (subChars.containsKey(c)) {
                repeatIndex = subChars.get(c);
                break;
            }
            subChars.put(c, j);
        }
        if (repeatIndex != -1) {
            // 找到重复元素,从第一个重复元素的下一个下标开始遍历
            i = repeatIndex + 1;
            repeatIndex = -1;
        } else {
            i++;
        }
        maxSize = Math.max(maxSize, subChars.size());
        subChars.clear();
        float middleSize = chars.length / 2f;
        if (maxSize >= middleSize && i >= middleSize) {
            // 最大子串长度超过一半了,可以不用继续遍历了
            break;
        }
    }
    return maxSize;
}

滑动窗口

滑动窗口是字符串类问题的最常用的方法。在这道题目中,我们按区间进行字符串搜索,遇到重复字符,就从左区间开始删除,直到删除掉重复字符为止。

在这道题目中,滑动窗口其实相当于就是一个队列,比如例题中的 abcabcbb:

  1. 进入这个队列(窗口)为 abc,暂时满足题目要求
    滑动窗口

  2. 当再进入 a,队列变成了 abca
    滑动窗口

  3. 这时候不满足要求,所以,我们要移动这个队列,把队列的左边的元素移出就行了,一直到满足题目要求。
    滑动窗口

一直维持这样的队列,找出队列出现最长的长度时候,我们就求得最终答案。

public int lengthOfLongestSubstring(String s) {
    int len = s.length();
    // 最大长度
    int maxLength = 0;
    // 左指针
    int left = 0;
    // 右指针
    int right = 0;
    // 子串队列
    Set<Character> subChars = new HashSet<>();
    while (left < len && right < len) {
        if (subChars.contains(s.charAt(right))) {
            // 子串重复,字符串从队首开始移除
            subChars.remove(s.charAt(left));
            // 移动左指针
            left++;
        } else {
            // 子串不重复,字符入队尾
            subChars.add(s.charAt(right));
            right++;
            // 记录最长不重复长度
            maxLength = Math.max(maxLength, right - left);
        }
    }
    return maxLength;
}

优化的滑动窗口

在滑动窗口时,上述的方法最多需要执行 2n 个步骤。事实上,它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时,我们可以立即跳过该窗口。

public static int lengthOfLongestSubstring(String s) {
    int len = s.length();
    // 最大长度
    int maxLength = 0;
    // 使用Map结构缓存字符和索引的映射
    Map<Character, Integer> map = new HashMap<>();
    // 滑动窗口
    for (int right = 0, left = 0; right < len; right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            // 找到重复子串,左指针跳到最后的重复位置
            left = Math.max(map.get(c), left);
        }
        int curLength = right - left + 1;
        // 取最大长度
        maxLength = Math.max(maxLength, curLength);
        // 缓存字符和下标映射
        map.put(c, right + 1);
    }
    return maxLength;
}

优化的滑动窗口2

针对上述优化方式,我们还可以进一步优化,不过这个方法相对有些投机取巧,各位看看就行

public static int lengthOfLongestSubstring(String s) {
//      Java(假设字符集为 ASCII 128)
//      以前我们没有对字符串 s 所使用的字符集进行假设。
//      当我们知道该字符集比较小的时侯,我们可以用一个整数数组作为直接访问表来替换 Map。
    int len = s.length();
    // 最大长度
    int maxLength = 0;
    // 使用128位数组缓存下标
    int[] index = new int[128];
    // 滑动窗口
    for (int right = 0, left = 0; right < len; right++) {
        char c = s.charAt(right);
        // 取index对应字符的缓存下标
        // 如果没有,则是默认值0
        // 若一旦有非零值,则代表有相同字符缓存到index数组中,则下标可跳到最后重复为止,再计算出不重复长度
        left = Math.max(index[c], left);
        int curLength = right - left + 1;
        // 取最大长度
        maxLength = Math.max(maxLength, curLength);
        // 缓存字符和下标映射
        index[c] = right + 1;
    }
    return maxLength;
}

这道题的解法中,暴力解法一定是不可取的,其实能写出滑动窗口解法就差不多了,优化方式都是加分项了。当然了,解题方法一定不止于此,大家可以继续深究!


更多技术干货,欢迎关注我!

qr