3. 无重复字符的最长子串 - Java 滑动窗口

原题地址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

题解

滑动窗口，初始化left和right指针为0

一开始将窗口扩展，right++一直到s.charAt(right+1)为重复元素，此时[left,right]为当前left下的最大窗口

将窗口收缩，left++一直到s.charAt(right+1)不再为重复元素，此时阻碍消失，right继续++至s.charAt(right+1)为重复元素

将每次扩展完后的窗口长度取最大值即为最长的子字符串

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0)return 0;

        int left=0,right=0,max=Integer.MIN_VALUE;
        Set<Character> set=new HashSet<>();
        set.add(s.charAt(0));

        while (left<s.length()){
            //扩展窗口
            while (right<s.length()-1&&!set.contains(s.charAt(right+1))){
                right++;
                set.add(s.charAt(right));
            }
            max=Math.max(max,right-left+1);

            //当扩展完毕后right为数组末尾，则接下来窗口值只能缩减，不存在更大的解，跳出循环
            if(right==s.length()-1)break;

            //收缩窗口
            while (left<s.length()&&s.charAt(left)!=s.charAt(right+1)){
                set.remove(s.charAt(left));
                left++;
            }
            set.remove(s.charAt(left));
            left++;
        }
        return max;
    }
}