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

题目链接：3. 无重复字符的最长子串 

首先想到的就是暴力破解，直接两层循环遍历，因为它说求无重复，那就可以用 set 来存储遍历到的字符，如果遍历到了同样的字符(在 set 中存在)，就直接跳出第二层循环，然后比大小，将计数器 count 更新成 set 的元素个数和 count 的最大值，最后返回 count 即可。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int count = 0, left = 0, right = 0, len = s.length();

        for (int i = 0; i < s.length(); i++) {
            Set<Character> set = new HashSet<>();
            set.add(s.charAt(i));

            for (int j = i + 1; j < s.length(); j++) {
                if (set.isEmpty() || !set.contains(s.charAt(j))) {
                    set.add(s.charAt(j));
                } else {
                    // 遇到了同样的字符
                    break;
                }
            }
            count = Math.max(set.size(), count);
        }

        return count;

    }
}

但是仔细想想，两层循环其实是可以优化的，可以用滑动窗口来做， 定义两个指针 left 和 right，还是用 set 来记录遍历的字符，让 right 一直往后走(在没越界的前提下)，并将遇到的字符加到 set 里，直到遇到同样的字符 ch 才停下来，然后就判断一下，right 是否越界，越界了就判断下 set 的个数和 count 谁大并将 count 更新成它们中的最大值，然后返回 count。如果没越界，还是得判断 count 与 set 的最大值，然后再让 left 一直出窗口，并将 left 遇到的字符从 set 中删除，直到 left 遇到 ch，才停下来，然后 left++，right++，跳过 ch，继续往后找连续无重复串，最后返回 count 即可。 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int count = 0, left = 0, right = 0, len = s.length();
        Set<Character> set = new HashSet<>();
        while (right < len) {
            // 进窗口
            while (right < len && (set.isEmpty() || !set.contains(s.charAt(right)))) {
                set.add(s.charAt(right));
                right++;
            }
            // 判断
            if (right >= len) {
                count = Math.max(count, set.size());
                break;
            }
            char c = s.charAt(right);
            count = Math.max(count, set.size());
            
            // 出窗口
            while (left < right && s.charAt(left) != c) {
                set.remove(s.charAt(left));
                left++;
            }
            left++;
            right++;
        }

        return count;

    }
}