【技术分享-真题实战】求最长无重复字符子串 （Java）

题目详情

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

示例 1:

输入: s = "abcabcbb"

输出: 3

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

示例 2:

输入: s = "bbbbb"

输出: 1

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

示例 3:

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

题目分析：

1、求没有重复字符的子串

2、这个子串最长是多少？

3、最长子串必须是连续的

做题思路：

连续的、长度不确定、没有重复

可以使用滑动窗口思想，在使用set去重

什么是滑动窗口思想？

1、双指针思想，两个指针之间的部分可以认为是一个窗口。

2、有固定大小窗口和大小动态变化的窗口。

3、将两个嵌套循环转化为 单层循环。

什么情况下使用滑动窗口？

1、给出的数据结构是数组或者字符串

2、求字串、子序列或者求某个具体值

3、这种问题一般能通过暴力求解

滑动窗口的思路

左右双指针，右指针右移寻找符合的条件，左指针右移，压缩区间

本题思路

1、定义左右指针，左右指针之间的部分代表窗口

2、判断窗口内有没有重复的数

3、如果窗口内有重复的数，左指针右移，缩小范围

4、窗口内没有重复的数，右指针右移，扩大范围

5、记录区间长度

注：

Set 中的contains方法可以用来判断集合中是否包含某元素，Set是一种无序且不允许重复的集合。Set的contains方法使用Hash算法，使用哈希值来快速定位元素的位置，不需要遍历一遍集合。

List的contains方法在判断元素是否存在时需要遍历整个列表，资源较大。

publicstaticintmaxLengthStr(Stringstr){
intmaxLength=0;
Set<Character>set=newHashSet<>();
//定义左右指针，右指针右移扩大窗口区间for(intleft=0,right=0;right<str.length;right++){
//使用set存储并判断窗口中是否包含右指针指向的元素if(set.contains(str.charAt(right))){
//包含说明有重复的，需要从左边开始删除，直到没有重复的while(str.charAt(left) !=str.charAt(right)){
//使用while循环，依次从左边开始删除，直到没有重复的set.remove(str.charAt(left));
left++;
            }
left++;
        }else{
//如果窗口中的元素不等于右指针元素，将右指针元素添加到set中set.add(str.charAt(right))
//将最大长度存入maxLengthif(set.size()>maxLegth){
maxLegth=set.size();
            }
        }
    }
returnmaxLegth;
}