侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表, 滑动窗口】无重复字符的最长子串

GabrielxD
2022-06-04 / 0 评论 / 0 点赞 / 29 阅读 / 749 字 / 正在检测是否收录...

题目

3. 无重复字符的最长子串

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer II 016. 不含重复字符的最长子字符串


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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

解题

方法一:哈希表 滑动窗口

思路

维护一个map集合(map),键表示字符,值表示该字符上一次出现的索引(因为 s 的范围在ASCII码内,所以此处用一个长度256的数组代替)。

初始化所有字符上一次出现的索引为 -1 既可以表示还没在字符串中出现过。

维护两个指针(start, end)用来表示滑动窗口,两个指针都从 0 开始,遍历字符串:

  • 取出 end 指针指向的字符 ch,把 ch 上次出现的索引 + 1 与 start 作比较,取较大的作当前滑动窗口的左边界。
  • 用滑动窗口的长度更新 max,维护一个最长的滑动窗口长度。
  • ch 上次出现的索引更新为 endend 自增。

最后返回 max

代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] map = new int[256];
        Arrays.fill(map, -1);
        int max = 1;
        for (int start = 0, end = 0; end < n; end++) {
            char ch = s.charAt(right);
            start = Math.max(start, map[ch] + 1);
            max = Math.max(max, end - left + 1);
            map[ch] = end;
        }
        return max;
    }
}

优化

s 由英文字母、数字、符号和空格组成,所以 map 长度为 '~' - ' ' +1 就够用了。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[] map = new int[95];
        Arrays.fill(map, -1);
        int max = 1;
        for (int start = 0, end = 0; end < n; end++) {
            char ch = s.charAt(end);
            start = Math.max(start, map[ch - ' '] + 1);
            max = Math.max(max, end - start + 1);
            map[ch - ' '] = end;
        }
        return max;
    }
}

模板

【算法】工具 / 模板 - 滑动窗口 模板,更容易理解。

class Solution {
    static final int HASH_LEN = 128;

    public int lengthOfLongestSubstring(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length;
        int[] window = new int[HASH_LEN];
        int left = 0, right = 0;
        int maxLen = 0;
        while (right < n) {
            char curr = chs[right++];
            if (++window[curr] < 2) {
                maxLen = Math.max(maxLen, right - left);
            } else {
                while (true) {
                    curr = chs[left++];
                    if (--window[curr] == 1) break;
                }
            }
        }
        return maxLen;
    }
}
0

评论区