1. //给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 
    2. //
    3. // 
    4. //
    5. // 示例 1: 
    6. //
    7. // 
    8. //输入: s = "abcabcbb"
    9. //输出: 3 
    10. //解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    11. // 
    12. //
    13. // 示例 2: 
    14. //
    15. // 
    16. //输入: s = "bbbbb"
    17. //输出: 1
    18. //解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    19. // 
    20. //
    21. // 示例 3: 
    22. //
    23. // 
    24. //输入: s = "pwwkew"
    25. //输出: 3
    26. //解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    27. //     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
    28. // 
    29. //
    30. // 示例 4: 
    31. //
    32. // 
    33. //输入: s = ""
    34. //输出: 0
    35. // 
    36. //
    37. // 
    38. //
    39. // 提示： 
    40. //
    41. // 
    42. // 0 <= s.length <= 5 * 104 
    43. // s 由英文字母、数字、符号和空格组成 
    44. // 
    45. // Related Topics 哈希表 双指针 字符串 Sliding Window 
    46. // 👍 4992 👎 0

    子串是要求连续的，序列是可以不连续的。
    要求子串中的符号不重复, 那么可以使用set来存储已经存在的字符，当发现重复的时候，依次将左边界的字符移出，直到不重复

    1. class Solution {
    2.     public int lengthOfLongestSubstring(String s) {
    3.         HashSet<Character> set = new HashSet<>();
    4.         int left = 0;
    5.         int right = 0;
    6.         int res = 0;
    7.         for (int i = 0; i < s.length(); i++) {
    8.             // 如果当前要加入的字符已经在哈希表里，
    9.             while (set.contains(s.charAt(i))) {
    10.                 // 依次将左边界的字符移出，直到要加入的字符也被移出
    11.                 set.remove(s.charAt(left));
    12.                 left ++;
    13.             }
    14.             set.add(s.charAt(right));
    15.             right ++;
    16.             // 最大长度就是left和right中间的这段子串
    17.             res = Math.max(res, right - left);
    18.         }
    19.         return res;
    20.     }
    21. }

    在上面可以使用boolean数组来代替HashSet，因为已经给定了s中字符的范围

    
class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] set = new boolean[128];
        int left = 0;
        int right = 0;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            while (set[s.charAt(i)]) {
                set[s.charAt(left)] = false;
                left ++;
            }
            set[s.charAt(right)] = true;
            right ++;
            res = Math.max(res, right - left);
        }
        return res;
    }

}

    因为使用滑动窗口，所以依次检索字符串依次，在哈希表中判断的时间复杂度是O(1)，因此总体时间复杂度为O(N), N为s的长度。
    空间复杂度为O(M),M为s中字符的范围。