刷题日记2. 无重复字符的最长字串 -LeetCode_无重复的子串是什么意思

题目

给定一个字符串，求出其中不重复子串的最大长度。不重复子串的含义是，这里面的字母都是唯一的，不重复的。
举个例子：

s="abcabcbb"
输出:3
因为最长的不重复子串是"abc"
s="bbb"
输出:1
最为最长的不重复子串是"b"
s=""
输出:0
1
2
3
4
5
6
7
8

我的思路

这道题涉及到的知识：串 重复。说到重复我们就想到了Java中的Map List Set。尤其是Set，它的性质是：集合中的元素都是不重复的，如果添加一个Set集合中已有的元素到Set中则添加失败。那我们可以遍历这个字符串，每个字符做首字母，从首字母开始，依次向Set集合中放入字符，如果放入成功，则继续放入；如果放入失败，则最外层循环结束，并记录当前字符长度。

代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //if(s.length==0) return 0;
        Set<Character> set=new HashSet<>();
        int max=0,count=0;
        for(int i=0;i<s.length();i++){
            max=Math.max(max,count);
            count=0;
            set.clear();
            for(int j=i;j<s.length();j++){
                boolean flag=set.add(s.charAt(j));
                if(!flag){
                    break;
                }
                count++;
            }
        }
        return Math.max(max,count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

执行结果：

这个算法时间复杂度为O(n^2)，效率略低。

官方题解

滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口法
        Set<Character> set=new HashSet<>();
        int n=s.length();
        int ans=0,rk=-1;
        for(int i=0;i<n;i++){
            if(i!=0){
                set.remove(s.charAt(i-1));
            }
            while(rk+1<n && !set.contains(s.charAt(rk+1))){
                set.add(s.charAt(rk+1));
                rk++;
            }

            ans=Math.max(ans,rk-i+1);
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21