侧边栏壁纸
  • 累计撰写 106 篇文章
  • 累计创建 3 个标签
  • 累计收到 19 条评论
标签搜索

目 录CONTENT

文章目录

LeetCode刷题笔记-3.无重复字符的最长子串

卑微幻想家
2022-01-13 / 0 评论 / 0 点赞 / 167 阅读 / 3,369 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = ""
输出: 0

提示:

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

我的解法

public int lengthOfLongestSubstring(String s) {
    // 定义一个map用来,存放已经匹配的字符和索引
    Map<Character, Integer> resultMap = new HashMap<>();
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (!resultMap.containsKey(s.charAt(j))) {
                // 若不包含,说明没有重复,将当前字符放入map,并记录索引
                resultMap.put(s.charAt(j), j);
                // 记录当前最大长度
                maxLength = Math.max(maxLength, j - i + 1);
            } else {
                // 若包含,则下次从当前包含的索引处开始遍历
                i = resultMap.get(s.charAt(j));
                // 将map置空,重新用于新的子串
                resultMap = new HashMap<>();
                break;
            }
        }
    }
    return maxLength;
}
复杂度分析
  • 时间复杂度:O(N^2)
  • 空间复杂度:用map装结果,O(G) G为字符集的大小

官方解法

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}
滑动窗口
思路和算法

我们先用一个例子考虑如何在较优的时间复杂度内通过本题。

我们不妨以示例一中的字符串 abcabcbb 为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:

  • 以 (a)bcabcbb(a)bcabcbb 开始的最长字符串为 (abc)abcbb(abc)abcbb;
  • 以 a(b)cabcbba(b)cabcbb 开始的最长字符串为 a(bca)bcbba(bca)bcbb;
  • 以 ab(c)abcbbab(c)abcbb 开始的最长字符串为 ab(cab)cbbab(cab)cbb;
  • 以 abc(a)bcbbabc(a)bcbb 开始的最长字符串为 abc(abc)bbabc(abc)bb;
  • 以 abca(b)cbbabca(b)cbb 开始的最长字符串为 abca(bc)bbabca(bc)bb;
  • 以 abcab(c)bbabcab(c)bb 开始的最长字符串为 abcab(cb)babcab(cb)b;
  • 以 abcabc(b)babcabc(b)b 开始的最长字符串为 abcabc(b)babcabc(b)b;
  • 以 abcabcb(b)abcabcb(b) 开始的最长字符串为 abcabcb(b)abcabcb(b)。

发现了什么?如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第k个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1 个字符作为起始位置时,首先从k+1到rk的字符显然是不重复的,并且由于少了原本的第k个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。

这样一来,我们就可以使用「滑动窗口」来解决这个问题了:

  • 我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的 rk;
  • 在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;
  • 在枚举结束后,我们找到的最长的子串的长度即为答案。
判断重复字符

在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。

复杂度分析
  • 时间复杂度:O(N),其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

  • 空间复杂度:O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有 ∣Σ∣ 个,因此空间复杂度为 O(∣Σ∣)。

总结

我和官方解法相比,多用了一个循环,导致空间复杂度增加,但是我记录了索引,可以跳动到重复字符的下一个位置,相比官方解法的一个个滑动,少了些无效循环。

优化方案

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> resultMap = new HashMap<>();
    int maxLength = 0; int startIndex = 0;
    for (int i = 0; i < s.length(); i++) {
        if (!resultMap.containsKey(s.charAt(i))) {
            resultMap.put(s.charAt(i), i);
            maxLength = Math.max(maxLength, i - startIndex + 1);
        } else {
            i = resultMap.get(s.charAt(i));
            startIndex = i + 1;
            resultMap = new HashMap<>();
        }
    }
    return maxLength;
}

网友方案

public int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0, start = 0;
    for (int end = 0; end < s.length(); end++) {
        char ch = s.charAt(end);
        if (map.containsKey(ch)){
            start = Math.max(map.get(ch)+1,start);
        }
        max = Math.max(max,end - start + 1);
        map.put(ch,end);
    }
    return max;
}

这个方案更加的精妙,和我一样记录了索引的位置,但是在改变start和保存map的时候操作比我优雅的多。值得学习。

0

评论区