来源：力扣（LeetCode）
链接：
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目描述

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

题目分析

滑动窗口

思路：两个指针表示字符串中的某个子串（或窗口）的左右边界。左指针向右移动一格，移除一个字符；不断向右移动 右指针。哈希集合，记录每个字符是否出现过，

代码实现

public class LengthOfLongestSubstring_3 {

    public static void main(String[] args) {
        LengthOfLongestSubstring_3 main = new LengthOfLongestSubstring_3();
        int result = main.lengthOfLongestSubstring("abcdee");
        System.out.println("result:" + result);
    }


    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        int end = 0;
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            // 不断向右移动 右指针
            while (end < s.length() && !occ.contains(s.charAt(end))){
                occ.add(s.charAt(end));
                end++;
            }
            int length = end - I;
            if (result < length) {
                result = length;
            }

        }
        return result;
    }

    /**
     * 效率太低
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring1(String s) {
        int result = 0;
        int length = 0;
        int nextEndStart = 0;

        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }

            // 不断向右移动 右指针
            for (int end = nextEndStart; end < s.length(); end++) {
                if (occ.contains(s.charAt(end))) {
                    length = end - I;
                    nextEndStart = end;
                    break;
                }
                occ.add(s.charAt(end));
                if(end == s.length() - 1){
                    length =  end - i + 1;
                }
            }
            if (result < length) {
                result = length;
            }
        }

        System.out.println("result:" + result);
        return result;
    }

}

复杂度

• 时间复杂度：O(n)，其中 n 是字符串长度。
• 空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），
  ∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！