摘要：题目解析题目含义很简单，即求出没有字符重复的子字符串的长度。例如很明显就是个由完全重复字符组成的字符串，所以它的答案长度为。所以综合来看该算法的效率为。
题目
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
题目含义很简单，即求出没有字符重复的子字符串的长度。例如bbbbb很明显就是个由完全重复字符组成的字符串，所以它的答案长度为1。
解法1 : 遍历字符串构成无重复字符字符串最简单的方法就是通过遍历字符串的每一个字符，循环的构造子字符串，遇到重复字符便停止，然后得出最长长度的那个字符串。
public static int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for(int index = 0 ; index=0){
if(temp.length()>maxLength)
maxLength = temp.length();
break;
}else{
temp.append(s.charAt(buffer));
}
}
// 如果该子串的长度大于当前最大长度，那么替换为最长长度
if(temp.length()>maxLength){
maxLength = temp.length();
}
}
return maxLength;
}
这个方法非常好理解，但是唯一的问题就是效率非常低,在外层有两层循环，在寻找字符操作时(temp.indexOf(currStr))也要循环一遍，所以该算法的复杂度为O(n^3)
解法2 滑动构造子串 public static int lengthOfLongestSubstring(String s){
// 非空校验
if(s==null || s.isEmpty()){
return 0;
}
int length = s.length();
// 定义滑动标志位:indexOne，indexTwo s[indexOne]~s[indexTwo]之间的字符串组成一个不重复字符的子
// 串
int indexOne = 0 , indexTwo = 0;
int maxLength = 0;
Set set = new HashSet<>();
while(indexOne < length && indexTwo < length){
// 如果set不包含新字符
if(!set.contains(s.charAt(indexTwo))){
// 那么indexTwo++ ，同时将新字符添加到set中
set.add(s.charAt(indexTwo++));
// 当前子串长度为 indexTwo - indexOne
maxLength = Math.max(maxLength , indexTwo - indexOne);
}else{
set.remove(s.charAt(indexOne++));
}
}
return maxLength;
}
滑动构造子串的意思即通过两个索引indexOne，indexTwo动态构造子串，如果下一个字符没重复，那么indexTwo+1，如果下一个字符已重复，那么indexOne+1。
在最好的情况下，例如输入"abcde"的时候，下一个字符一直是新的字符，那么indexTwo可以一直+1，直到字符串被遍历完，这时候的效率为O(n)。
在最差的情况下，例如输入"bbbbb"的时候，下一个字符一直是重复字符，那么程序一直执行indexTwo+1后indexOne+1的循环，也即indexOne和indexTwo分别遍历了一遍了字符串，那么这时候的效率为O(2n)。
所以综合来看该算法的效率为O(n)。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72391.html
摘要：解题思路本题借助实现。如果字符未出现过，则字符，如果字符出现过，则维护上次出现的遍历的起始点。注意点每次都要更新字符的位置最后返回时，一定要考虑到从到字符串末尾都没有遇到重复字符的情况，所欲需要比较下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...
摘要：原问题我的沙雕解法无重复字母存在重复字母挨打最暴力的无脑解法，耗时。。。 原问题 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbb Output: 3 Explanation: The answer is a...
摘要：建立数组，存储个字符最近一次出现的位置。首次出现某字符时，其位置标记为，并用无重复字符计数器记录无重复字符的长度，再在更新其最大值。循环完整个字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...
摘要：题目详情题目要求输入一个字符串，我们要找出其中不含重复字符的最长子字符串，返回这个最长子字符串的长度。对于字符串中的每一个字符，先判断中是否已经存在这个字符，如果不存在，直接将添加到，如果已存在，则新的字符串就从不含前一个字符的地方开始。 题目详情 Given a string, find the length of the longest substring without repe...
摘要：哈希表是最自然的想法。在遍历字符串时，我们先根据哈希表找出该字符上次出现的位置，如果大于等于子字符串首，便更新子字符串首。结束后，将该字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...
阅读 875·2021-11-16 11:45
阅读 2104·2021-10-09 09:44
阅读 1319·2019-08-30 14:03
阅读 1076·2019-08-26 18:28
阅读 3309·2019-08-26 13:50
阅读 1692·2019-08-23 18:38
阅读 3439·2019-08-23 18:22
阅读 3559·2019-08-23 15:27
