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

共 1226字,需浏览 3分钟

 ·

2020-09-15 09:19

每天 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 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 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;
}





感谢阅读



浏览 36
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报