给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
- 示例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 示例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
- 示例3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：首先判断极限值，如果数组长度为0，就直接返回。定义一个最大长度num，创建一个HashSet存储无重复的元素，从每一个位置开始遍历，调用test()函数。test()函数中，首先要确定递归的出口，然后分为两种情况，如果set中有i位置的元素，就直接返回结果，因为无法继续构成连续的子串。如果set中没有i位置的元素，就尝试将i位置的元素添加到set中，进行下一层的递归调用，直到输出结果。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0) {
return 0; //如果数组长度为0，直接返回结果
}
int num = 0; //定义无重复字符的最大长度
Set<Character> answer = new HashSet<>(); //利用set存储无重复的元素
for(int i =0; i < s.length() && s.length() - i >num ; i++) { //遍历每一个元素
int mes = test(s, i, 0, answer); //调用方法，获得该位置开始无重复的最大长度
if(num < mes) { //如果大于，就更新最大长度
num = mes;
}
answer.clear(); //清空set，以便重新开始
}
return num; //返回结果
}
private int test(String s, int i, int count, Set<Character> answer) {
if(i >= s.length()) { //如果已经遍历了所有，就返回结果
return count;
}
char temp = s.charAt(i); //获取i位置上的值
if(answer.contains(temp)) { //查看set中是否有temp
return count; //如果有，就结束调用，直接返回
}
answer.add(temp); //如果set中不存在temp，就尝试把temp加入到集合中
int msg=test(s, i+1, count+1, answer); //递归调用下一层
return msg; //返回结果
}
}
思路：这里采用的是滑动窗口的方法。同样创建一个set来存放没有重复的元素，并且设置左指针i=0，右指针j=0。进入while循环，判断set中是否含有j位置元素的指针，如果不含有，则将j位置的元素添加到set中，并且j右移一位，同时更新最大长度。如果含有，则表示从i位置开始的最大长度子串已经确定，那么就从set中删除i位置上的元素，同时i右移一位。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0) {
return 0; //如果字符串长度为0就直接返回
}
int i = 0, j = 0; //设置左指针i和右指针j
int num = 0; //最大长度
Set<Character> answer = new HashSet<>(); //创建一个set来存放没有重复的元素
while(i < s.length() && j < s.length()) { //限定边界条件
if(!answer.contains(s.charAt(j))) { //如果set中不含有j位置的元素
answer.add(s.charAt(j++)); //将j位置元素添加到set中，并且j+1
num = Math.max(num, j - i); //更新最大长度
}else { //如果set中含有j位置的元素
answer.remove(s.charAt(i++)); //删除i位置上的元素，i+1
}
}
return num; //返回结果
}
}
网友评论