LeetCode 无重复字符的最长子串【滑动窗口】

旧城等待， 2022-09-11 01:22 152阅读 0赞

# 1 题目描述 #

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

**示例 1:**

输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 2:**

输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例 3:**

输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

**示例 4:**

输入: s = ""
    输出: 0

**提示：**

0 <= s.length <= 5 * 104
    s 由英文字母、数字、符号和空格组成

# 2 解题 #

## 2.1 窗口滑动 ##

public int lengthOfLongestSubstring(String s) { 
            if (s.length() == 0) { 
                return 0;
            }
            int rs = 0;
            Set<Character> set = new HashSet<>();
            int right = 0;
            for (int left = 0; left < s.length(); left++) { 
                char c = s.charAt(left);
                //右移动
                while (right < s.length() && !set.contains(s.charAt(right))) { 
                    set.add(s.charAt(right));
                    right++;
                }
    
                if (right - left > rs) { 
                    rs = right - left;
                }
    
                if (right==s.length()){ 
                    break;
                }
    
                //去除头
                set.remove(c);
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

## 2.2 巧解 ##

public int lengthOfLongestSubstring(String s) { 
            if (s.length() == 0) { 
                return 0;
            }
            Map<Character, Integer> map = new HashMap<>();
            int left = 0, right = 0, rs = 0;
            while (right < s.length()) { 
                char c = s.charAt(right);
                if (map.containsKey(c) && left < map.get(c) + 1) { 
                    //左指针移动到 右边指针
                    left = map.get(c) + 1;
                }
                map.put(c, right);
                if (right - left + 1 > rs) { 
                    rs = right - left + 1;
                }
                //右指针右移动
                right++;
    
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0933a02c01e2414e8e02522b26ec3940.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/a0a0f82501f14ad388fe89581289988d.png