leecode刷题3.无重复字符的最长子串【Java】

2022-07-22 22:52:06

一、题目

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

二、方法一：暴力求解

逐个生成子字符串
看它是否含有重复的字符

public int lengthOfLongestSubString(String s){
    int n = s.length();
    if(n<=1)return n;
    int maxLen = 1;
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(allUnique(s,i,j)){		//判断i到j的区间中是否有重复的元素
                maxLen = Math.max(maxLen,j-i+1);//如果不存在重复的元素则更新maxLen
            }
        }
    }
    return maxLen;
}
//同一个子串会进行多次判断是否存在重复字符
private boolean allUnique(String s,int start,int end){
    Set<Character> set = new HashSet<>();
    for(int i=start;i<=end;i++){
        if(set.contains(s.charAt(i))){		//如果区间中存在重复的元素则返回false
            return false;
        }
        set.add(s.charAt(i));
    }
    return true;	//返回true没有重复的元素
}

时间复杂度为O(n³)

空间复杂度为O(n)

会超时

三、方法二：滑动窗口

暴力求解存在重复计算，同一个子串会进行多次判断是否存在重复字符

优化：只需要判断s[i,j)中判断是否存在s[j]即可，如果存在s[j]则说明存在重复元素

核心思路：需要不断移动右边界，因为窗口越大越好，如果移动到某一个元素在当前窗口中已经存在，则需要移动左边界来缩小窗口，从而剔除掉重复的元素

定义两个边界left和right，第一个不存在重复元素，将右边界right往右边移动
右移后，此时窗口(子串)最大长度为2，更新maxLength
继续右移，此时right所指字符在之前窗口中已经存在，此时应该缩小窗口从而将重复字符剔除窗口，就需要移动左边界left
左边界移动后，窗口中依旧存在重复字符w，继续右移left
这时left和right指向同一个元素，窗口中没有重复字符，就需要右移right扩大窗口
右移right后，判断在窗口中没有重复字符，计算长度为2，和maxLenght相等，不用替换，继续右移右边界right
此时窗口中不存在重复元素e，此时窗口长度为3，大于之前的maxLength2，则需要更新maxLength，此时right继续右移
右移后，在窗口中已经存在相同元素w，则需要移动左边界left来缩小窗口剔除重复元素
这时left所指为k，在窗口中不存在重复元素，继续右移right
right移除字符串，结束循环

时间复杂度为O(n)，每个字符最多遍历两遍

空间复杂度为O(n)，需要将字符放在某种数据结构中，这种数据结构需要快速判断一个字符是否存在于这个窗口中，就需要一个HashSet来存储字符

public int lengthOfLongestSubString(String s){
    int n = s.length();
    if(n<=1)return n;
    int maxLen = 1;
    
    int left = 0,right = 0;	//左边界和右边界
    Set<Character> window = new HashSet<>();	//利用hashSet存储字符
    while(right<n){		//处理窗口
        char rightChar = s.charAt(right);	//首先处理右边字符
        //判断窗口是否包含右边字符，如果包含则需要移动左边界来缩小窗口剔除重复元素
        while (window.contains(rightChar)){	
            window.remove(s.charAt(left));
            left++;
        }
        maxLen = Math.max(maxLen,right-left+1);
        window.add(rightChar);
        right++;
    }
    return maxLen;
}

优化：

以上当在窗口中存在重复字符，是一个一个字符的缩小窗口(一步一步的移动左边界left，效率较慢)

可以通过记住每个字符在字符串中的索引，当遇到重复字符的时候，就可以直接跳到重复字符的后面

可以使用HashMap存放遍历过的每个字符，来记录其位置

遍历字符串记录每个字符出现的位置，如果存在重复的元素，则将左边界left直接跳到重复元素的后面

此时w的索引位置变为最后一次的3，继续右移right

没有重复的元素则记录其索引，当移动到最后一位w，有重复元素，则拿到之前记录的w后一个元素的位置为4，将其赋给left，则可以快速剔除掉重复元素

public int lengthOfLongestSubString(String s){
    int n = s.length();
    if(n<=1)return n;
    int maxLen = 1;
    
    int left = 0,right = 0;	//左边界和右边界
    //利用hashMap存储字符的索引位置
    Map<Charcter,Integer> window = new HashMap<>();	
    //处理窗口
    while(right<n){		
        //首先处理右边字符
        char rightChar = s.charAt(right);	
        //如果rightChar之前在window中没有，则返回-1；如果存在则返回rightChar所在位置
        int rightCharIndex = window.getOrDefault(rightChar,-1);
        
        //将当前right所指位置赋值+1给left
        if(rightCharIndex == -1) {
           // 无重复，不滑动
        } else if(rightCharIndex < left) {
           // 脏数据，不滑动
           // 因为我们在往前移动 left 的时候，并没有删除窗口 window 中的数据
           // 所以，当我们从窗口中查找 rightChar 对应的元素的时候，就会找到它对应的索引是小于 left，也就是在 left 左边，
           // 因为这个字符在之前出现过。这种情况是不需要移动 left 的，因为在 left 到 right 的窗口内还没有重复字符的
        } else {
           left = rightCharIndex + 1;
        }
        
        maxLen = Math.max(maxLen,right-left+1);
        window.put(rightChar,right);
        right++;
    }
    return maxLen;
}

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

码农公寓

一、题目

二、方法一：暴力求解

三、方法二：滑动窗口

相关文章