3 无重复字符的最长子串

一、题目

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

二、题解

思路：滑动窗口

通过 right 指针向右扩张窗口，并利用 HashSet 实时检查字符是否重复；一旦 curChar 已存在，则不断右移 left 指针并从集合中移除字符，直到窗口内重新保证无重复。每次移动都会计算 right - left + 1 来更新最长长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {

        int maxLength = 0;
        // 【核心数据结构】HashSet 充当我们的“滑动窗口”，用来记录当前窗口内有哪些不重复的字符
        Set<Character> set = new HashSet();

        // left 是窗口的“左侧边界”
        int left = 0;

        // 【窗口扩张】right 是窗口的“右侧边界”，它主动向右移动，不断把新字符拉进窗口
        for(int right = 0; right < s.length(); right++) {
            Character curChar = s.charAt(right);

            // 【窗口收缩】重点！！！
            // 如果发现新进来的字符 curChar 已经在窗口（set）里了，说明产生了重复！
            while(set.contains(curChar)) {
                // 此时必须让“左侧边界” left 往右挪，把最左边的字符踢出窗口，
                // 直到把那个跟 curChar 重复的字符“吐出来”为止，才能恢复窗口内的唯一性。
                set.remove(s.charAt(left));
                left++;
            }

            // 冲突解决（或原本就没有冲突），把新的字符正式加入窗口
            set.add(curChar);

            // 算一下当前窗口的长度 (right - left + 1)，看看有没有打破历史最长记录
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(min(m,n))O(min(m, n))

评论