1、Algorithm
题目：
描述：
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例1:
输入:"abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc"，所以其长度为3。
示例2:
输入:"bbbbb"输出:1解释:因为无重复字符的最长子串是"b"，所以其长度为1。
示例3:
输入:"pwwkew"输出:3解释:因为无重复字符的最长子串是"wke"，所以其长度为3。请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。
思路1：记录一个已访问字符Set，从头开始遍历，每遍历一个字符，判断当前字符是否在set出现过，如果出现，则记录之前的子串长度，并与最大子串长度对比，保留最大值，然后清空重复字符之前的字符，然后接着遍历到结束。
代码：
publicclassSolution{publicintlengthOfLongestSubstring(Strings){intn=s.length();SetCharacterset=newHashSet();intans=0,i=0,j=0;while(injn){if(!set.contains(s.charAt(j))){set.add(s.charAt(j++));ans=Math.max(ans,j-i);}else{set.remove(s.charAt(i++));}}returnans;}}
思路2：思路1的方式每次出现重复的时候都需要把set中重复字符之前的字符清理掉，比较消耗时间，理论上重复之前的字符已经用不到了，下一个子串从重复字符的下一个位置开始，因此我们想办法把每个字符的索引存起来，考虑到我们用基本的ASCII字符只有个，我们可以申请一个的数组来存储字符索引。
代码：
classSolution{publicintlengthOfLongestSubstring(Strings){if(s==null
s.length()==0){return0;}if(s.length()==1){return1;}int[]index=newint[];intmaxLen=0;//滑动窗口思想for(inti=0,j=0;js.length();j++){//如果索引数组存在当前字符，则取索引数组中//字符的索引与当前子串起始位置i比对，取最大值i=Math.max(index[s.charAt(j)],i);maxLen=Math.max(maxLen,j-i+1);index[s.charAt(j)]=j+1;}returnmaxLen;}}
2、Review
[HuaweiShowstheChineseInternetwillWin]
转载请注明：http://www.quwenlai.com/zejz/4755.html
