Leetcode刷题100天—3. 无重复字符的最长子串(滑动窗口+集合+双指针)—day21

r囧r小猫 2022-08-28 14:53 97阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210828220024172][]

#### [3. 无重复字符的最长子串][3.] ####

难度中等6009收藏分享切换为英文接收动态反馈

给定一个字符串 `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` 由英文字母、数字、符号和空格组成

package 滑动窗口;
    
    import java.util.HashSet;
    import java.util.Set;
    
    public class _3_无重复字符的最长子串 { 
    // 集合+滑动窗口原理+双指针
        public int lengthOfLongestSubstring(String s) { 
    // 通过右指针遍历字符到集合中，如果集合发现重复字符就退出循环,然后获取之前的长度,
    // 在通过左指针慢慢取出之前在集合中的数，直到没有重复字符出现
        	
    // 定义左右指针left,right,和最大值ans
        	int ans=0,left=0,right=0;
    // 定义集合
        	Set<Character> set=new HashSet<>();
        	
    // 第一层遍历左指针,取出集合中的数
        	int len=s.length();
        	for(;left<len;left++) { 
    // 如果left不为0,说明要么right到顶，要么存在相同元素,如果是第二种就不断移除
        		if (left!=0) { 
    // left左指针向左移动一格去除,因为之前++,left变成1,我们要移除第一个数,
    // 若是下面遍历还发现有相同元素，left=2，在移除第一个数
    				set.remove(s.charAt(left-1));
    			}
        		
    // 通过右指针,将元素遍历到集合中,如果超过长度或者集合中已经存在该元素就停止
        		while(right<len&&!set.contains(s.charAt(right))) { 
        			set.add(s.charAt(right));
        			// 不断地移动右指针
        			right++;
        		}
        		if (right<len) { 
        			ans=Math.max(ans, right-left);
    			}
    // 通过比较每个窗口的长度来取最大值,窗口大小就是左指针减去右指针
        		ans=Math.max(ans, right-left);
        	}
        	return ans;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210828220024172]: /images/20220828/0b2df88bb56e48a0b019373874a3dfd4.png
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/