5-101-(LeetCode- 3) 无重复字符的最长子串

arctic_fox / 2023-04-28 / 原文

1. 题目

2. 解法

思路：滑动窗口来遍历字符串

大致如下：

定义一个哈希集合和两个指针，分别表示窗口内的字符和窗口的左右边界。
定义一个变量，表示窗口的最大长度，也就是答案。
从左到右遍历字符串，每次移动右指针，把它指向的字符加入到哈希集合中。
如果哈希集合中已经存在这个字符，说明有重复，那么就移动左指针，把它指向的字符从哈希集合中删除，直到没有重复为止。
每次移动指针后，更新最大长度，取它和当前窗口长度的较大值。
当右指针到达字符串末尾时，返回最大长度。

具体实现

    public static int lengthOfLongestSubstring(String s) {

        if (s == null || s.length() == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int size = s.length();

        int start = 0, end = 0;

        HashSet<Character> set = new HashSet<>();

        for (int i = 0; i < size; i++) {

            char c = s.charAt(i);

            while (set.contains(c)) {
                set.remove(s.charAt(start));
                start++;
            }

            set.add(c);
            end++;
            max = Math.max(max, end - start);

        }

        return max;
    }