【每日一题】leetcode3无重复字符的最长子串

题目描述

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

示例

必威体育苹果app下载输入: s = "abcabcbb"

必威体育苹果app下载输出: 3 

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

题目分析

要求从字符串中找到最长的不含重复字符的子串,那么就存在一个区间[start,end],在这个区间内,每个字符不重复且长度最长。怎么找到这个区间呢?首先设置两个指针start和end,start指向区间开始,end指向区间结束,初始都指向s开始,同时我们需要知道字符是否出现过,此时申请一个set,记录start-end出现的字符,向右移动end指针,若没有出现,则加入该字符入set,继续向右移动,若已经出现,此时需要移动start指针的位置到之前该字符出现位置的下一个位置,继续移动end,这个方法有个官方的名字--滑动窗口。下面图解一下,更直观。

 

解法1

public int lengthOfLongestSubstring(String s) {
    //如果长度<=1直接返回
    if (s.length() <= 1) {
        return s.length();
    }
    //开始指针和结束指针均指向第一个位置
    int start = 0, end = 0;
    Set<Character> set = new HashSet<>();
    int max = 1;
    set.add(s.charAt(start));
    ++ end;
    while (start <= end && end < s.length()) {
        if (set.contains(s.charAt(end))) {
            //如果区间内出现过
            int ans = end - start;
            max = Math.max(max, ans);
            //将之前字符前的全部移除出去
            while(start < end && s.charAt(start) != s.charAt(end)) {
                set.remove(s.charAt(start));
                ++ start;
            }
            ++ start;
            ++ end;
        } else {
            set.add(s.charAt(end));
            ++ end;
        }
    }
    int ans = end - start;
    max = Math.max(max, ans);
    return max;
}

注:公众号每天早上更新哦~欢迎大家关注

 

posted @ 2022-01-20 15:36  Carol淋  阅读(7)  评论(0编辑