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

滑动窗口

题目要求的是最长的不含重复字符的子串，看到“子串”并且需要维护一段连续区间时，通常可以考虑滑动窗口。

用两个指针维护当前窗口 $[left, right)$，并用数组记录每个字符在窗口中是否出现过。每次将右端字符加入窗口前，若发现它已经在窗口内出现过，就不断移动左指针并删除左侧字符，直到这个重复字符被移出窗口。这样可以保证任意时刻窗口内都没有重复字符。

随后用当前窗口长度更新答案即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, n = s.length();
        int ans = 0;
        int[] map = new int[128];
        while (right < n) {
            char cur = s.charAt(right);
            right++;

            while (map[cur] == 1) {
                map[s.charAt(left)]--;
                left++;
            }
            map[cur]++;

            ans = Math.max(ans, right - left);
        }
        return ans;
    }
}