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

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

作者: 肚皮怪_Sun | 来源:发表于2019-06-03 15:06 被阅读0次

    示例一下三种情况:

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

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

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

    下面是关于这个问题我的思路——它本质其实是个队列的问题,如例题中“pwwkew”,刚进入这个队列满足条件的是“pw”,如果再进到下一步“w”,这时候的队列就变成了“pww”,显然已经不满足条件了。这时候就要移除队列左边的数,直到满足条件为止,“pww”=>“pw”=>“w”。继续之前再进入队列“wke”=>“wkew”=>"kew"。一直维持这样的队列,找出队列出现最长的长度。

    贴出代码的实现:

    public int lengthOfLongestSubstring(String s) {
            if (s == null) {
                return 0;
            }
    
            if (s.length() == 1) {
                return 1;
            }
            int res = 0;
            int l=0;
            int r=0;
            int length = s.length();
            HashSet<Character> set = new HashSet<>();
    
            while (l<length&&r<length){
                if(!set.contains(s.charAt(r))) {
                    set.add(s.charAt(r));
                    r++;
                    res=Math.max(res,r-l);
                }else {
                    set.remove(s.charAt(l));
                    l++;
                }
            }
            return res;
        }
    

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/ilucxctx.html