题目

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

示例

示例 1:

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

示例 2:

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

示例 3:

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

提示

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

个人代码-仅击败5%

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int size = 0;
        for (int i=0, j=0;i<s.length();i++) {
            String sub = s.substring(j, i+1);
            int index = isUniqueSub(sub);
            if(index == -1) {
                size = Math.max(size, sub.length());
            }else{
                j += index + 1;
            }
        }
        return size;
    }
    private int isUniqueSub(String sub) {
        Set<Character> set = new HashSet<>();
        for (int i=sub.length()-1;i>-1;i--) {
            if(set.contains(sub.charAt(i))) {
                return i;
            }
            set.add(sub.charAt(i));
        }
        return -1;
    }
}

官方题解

方法一：滑动窗口

思路和算法

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

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

以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb； 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb； 以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb； 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb； 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb； 以 abcab(c)bb 开始的最长字符串为 abcab(cb)b； 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b； 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。

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;
    }
}

其它题解

滑动窗口模板

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    } 
    //区间[left,right]符合题意，统计相关信息
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();//去重
        int res = 0;//结果
        for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
            char ch = ss[right];//right指向的元素，也是当前要考虑的元素
            while(set.contains(ch)) {//set中有ch，则缩短左边界，同时从set集合出元素
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);//别忘。将当前元素加入。
            res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
        }
        return res;
    }
}