力扣3. 无重复字符的最长子串

Problem: 3. 无重复字符的最长子串

题目描述

思路及解法

1.创建一个set集合存储最长的无重复的字符；
2.创建双指针p、q，每次当q指针指向的字符不在set集合中时将其添加到set集合中让q指针后移，并且更新无重复字符串的最大长度，当q指向的字符在set集合中时，抹去p指针指向的字符

复杂度

时间复杂度:

$O(n)$;其中$n$为字符串$s$的长度

空间复杂度:

$O(n)$

Code

class Solution {
    /**
     * Longest Substring Without Repeating Characters
     *
     * @param s Given string
     * @return int
     */
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int p = 0;
        int q = 0;
        int maxLen = 0;
        Set<Character> set = new HashSet<>();
        while (q < n) {
            char c = s.charAt(q);
            if (!set.contains(c)) {
                set.add(c);
                q++;
                if (q - p > maxLen) {
                    maxLen = q - p;
                }
                continue;
            }
            while (set.contains(c)) {
                set.remove(s.charAt(p));
                p++;
            }
        }
        return maxLen;
    }
}