Yuyy
Yuyy
LeetCode3. 无重复字符的最长子串

一、思路

这题也是滑动窗口类型,判断窗口内是否有重复值时,我使用的是集合+队列。集合判断是否重复,队列记录窗口位置。解题后看了下题解,才发现滑动窗口类型确实做少了,这题明明可以用通用解法:下标+map,下标记录窗口位置,map判断是否重复(泛型为<字符,出现的次数>)。

用集合+队列还有个坑:当窗口从未缩小时,是没有触发计算length,需要在返回结果时做处理。

二、题目

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

 

示例 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 由英文字母、数字、符号和空格组成
Related Topics
  • 哈希表
  • 双指针
  • 字符串
  • Sliding Window
  • \n

  • 👍 4922
  • 👎 0
  • 三、代码

    public int lengthOfLongestSubstring(String s) {
                Queue<Character> queue = new LinkedList<>();
                HashSet<Character> set = new HashSet<>();
                int left = 0;
                int right = 0;
                int length = 0;
                while (s.length() > right) {
                    char c = s.charAt(right);
                    if (set.contains(c)) {
                        length = right - left > length ? right - left : length;
                        right++;
                        queue.add(c);
                        char c1 = queue.poll();
                        left++;
                        while (c1 != c) {
                            set.remove(c1);
                            c1 = queue.poll();
                            left++;
                        }
                    } else {
                        set.add(c);
                        queue.add(c);
                        right++;
                    }
                }
                return right - left > length ? right - left : length;
            }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode3. 无重复字符的最长子串
    一、思路 这题也是滑动窗口类型,判断窗口内是否有重复值时,我使用的是集合+队列。集合判断是否重复,队列记录窗口位置。解题后看了下题解,才发现滑动窗口类型确实做少了,这题明明可…
    扫描二维码继续阅读
    2021-02-05
    友情链接
    标签
    文章归档
    近期文章