目录
二、思路讲解(暴力方法)
一、题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
提示：
s.length <= 40000
二、思路讲解
暴力方法，遍历字符串，以每一个字符作为开头，将它及后面的字符怼到HashSet中，如果怼不进去了，那就是重复了，此时集合的大小就是不重复的字串的大小。然后清空集合，再看下一个字符，直到遍历完整个字符串。效率较低。
三、Java代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int index;
HashSet<Character> set = new HashSet<>();
int big = 0;
for(int i=0; i<len; i++){
index = i;
set.clear();
//把字符后的每一个字符怼进集合中，直到怼不进（说明重复了）或者遍历完了字符串
while(index<len && set.add(s.charAt(index))){
index++;
}
big = Math.max(big, set.size());
}
return big;
}
}四、时空复杂度分析
时间复杂度： O(N^2)
空间复杂度： O(N)
五、代码优化
想想时间上的优化：能不能仅遍历一遍字符串呢？
我们可以使用滑动窗口的思想，或者是使用动态规划的思想。
再想想空间上的优化：能不能用常数级的空间呢？
可以用HashMap，在ASCII码內长度最多为128，占用空间为常数级。
1、滑动窗口
具体思路是：使用set存放滑动窗口内的所有字符。 set的大小即为滑动窗口的大小。
- 如果j指针处的字符能够插入set，证明不和滑动窗口内的字符重复，j指针后移，扩大窗口；
- 如果j指针处的字符不能插入set，说明字符出现重复，那就将i指针后移（同时从set中删掉i处字符），缩小窗口。
使用max始终保存set的长度的最大值。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>(); //滑动窗口内的所有字符
int max = 0; //最大无重复字串长度
int i=0;
int j=0;
while(j<s.length()){
if(set.add(s.charAt(j))){
//如果j处字符和窗口内字符不重复，j指针后移，扩大窗口
j++;
} else {
//如果j处字符和窗口内字符重复，i指针后移，缩小窗口（此时set内所有字符还是不重复的）
set.remove(s.charAt(i));
i++;
}
max = Math.max(max, set.size());
}
return max;
}
}同样的道理，使用队列代替哈希集合来保存滑动窗口里的值，可以减少几次无用的判断，但是效率降低了。
class Solution {
public int lengthOfLongestSubstring(String s) {
Queue<Character> queue = new LinkedList<>(); //滑动窗口内的所有字符
int max = 0; //最大无重复字串长度
int i=0;
int j=0;
while(j<s.length()){
if(!queue.contains(s.charAt(j))){
//如果j处字符和窗口内字符不重复，j指针后移，扩大窗口
queue.add(s.charAt(j));
j++;
} else {
//如果j处字符和窗口内字符重复，i指针后移到重复字符之后
while(queue.poll() != s.charAt(j)){
i++;
}
}
max = Math.max(max, queue.size());
}
return max;
}
}时间复杂度O（n）
空间复杂度O（n）
2、动态规划
遍历字符串，以每个字符作为结尾，curr表示以当前字符结尾的最大无重复长度，max保存最大的无重复长度。
在向后遍历的过程中，若第i个字符在前面出现过，假设出现在x位置，则curr为min{curr, i-x}，（大括号里的curr为前一个字符结尾的最大无重复长度）；若第i个字符在前面没出现过，则前一个长度直接+1即可：curr = curr+1。
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int max = 0; //最大无重复长度
int curr = 0; //当前无重复长度
for(int i=0; i<s.length(); i++){
Character c = s.charAt(i);
curr = Math.min((curr+1), (i-map.getOrDefault(c, -1)));
map.put(c, i);
max = Math.max(max, curr);
}
return max;
}
}时间复杂度： O(N)
空间复杂度： O(1)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125035.html
