1. 首页
  2. LeetCode

每日一道 LeetCode (46):无重复字符的最长子串

每日一道 LeetCode (46):无重复字符的最长子串

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:无重复字符的最长子串

题目来源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 1:

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

示例 2:

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

示例 3:

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

解题方案一:暴力方案

看到这道题的第一个反应是这题我做过!!

然后我往前一顿翻,结果嘛。。。

emmmmmmmmmmm。。。

没找着。

既然找不着那就开始想,这题是要求一个最长无重复的子串,重点总共就两点:

  • 无重复
  • 子串

最后是要求一个最长的长度,这其实就是把所有的不重复子串的长度穷举出来,然后取最大就完事儿。

经过上面的分析,我们成功的把这道题转化成了一个求不重复子串的问题。

思路是滑动窗口,首先子串肯定是有长度的,即使只有 1 也是有长度的。

这时,我们指定两个指针,一个左一个右,左右指针之间的内容实际上就是我们的子串,长度就是我们的子串长度。

两个指针位于初始位置时,开始移动右指针,然后每次移动以后判断指向的元素是否和之前已有的元素有重复,如果没有重复就一直向右移,直到有重复的为止,这就是我们的第一个子串,然后记录这个子串的长度。

接下来左指针右移一位,然后再重复上面的过程,一直到左指针移动完整个字符串,这时我们就遍历完成了所有的不重复的子串。

判断子串是否用重复可以通过数据结构来判断,通常常用的有哈希表。

接下来就是代码实现:

public int lengthOfLongestSubstring(String s) {
    Set<Character> setChars = new HashSet<>();
    int length = s.length();
    // 定义右指针
    int right = -1;
    // 定义返回结果
    int result = 0;
    for (int i = 0; i < length; ++i) {
        if (i != 0) {
            // 左指针右移一次,删掉前一个字符
            setChars.remove(s.charAt(i - 1));
        }
        while (right + 1 < length && !setChars.contains(s.charAt(right + 1))) {
            // 移动右指针,像 set 中添加字符
            setChars.add(s.charAt(right + 1));
            ++right;
        }
        result = Math.max(result, right - i + 1);
    }
    return result;
}

解题方案二:优化后

上面这个方案有个缺陷,就是每次左指针只是单纯的 + 1 ,实际上左指针可以直接移动到右指针 + 1 的位置,因为当前的子串已经有重复了,直接跳过就好了。

public int lengthOfLongestSubstring_1(String s) {
    int length = s.length(), result = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int left = 0, right = 0; right < length; right++) {
        // 如果含有右指针指向的元素,则移动左指针
        if (map.containsKey(s.charAt(right))) {
            left = Math.max(map.get(s.charAt(right)), left);
        }
        result = Math.max(result, right - left + 1);
        map.put(s.charAt(right), right + 1);
    }
    return result;
}

解题方案三:极致优化

上面的方案还有没有优化空间,当然有,我们对循环次数已经没办法优化了,那么还能优化的就剩下了判断当前字符是否存在。

比哈希表寻址还要快的可能有什么?当然是直接操作数组咯~~~

首先可以定义一个 128 位的数组,然后我们通过数组进行判断当前字符是否存在:

public int lengthOfLongestSubstring_2(String s) {
    int n = s.length();
    int result = 0;
    int[] charIndex = new int[128];
    for (int left = 0, right = 0; right < n; right++) {
        char c = s.charAt(right);
        left = Math.max(charIndex[c], left);
        result = Math.max(result, right - left + 1);
        charIndex[c] = right + 1;
    }
    return result;
}
转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code