2018年怎么做网站排名,灯罩技术支持东莞网站建设,镇江网页,贵州省交通建设工程质量监督局网站虽然是一道中等题#xff0c;但我5分钟就写完了#xff0c;而且是看完题就知道怎么写#xff0c;这一看就知道双指针#xff0c;一个左一个右#xff0c;右指针往后移如果没有重复的长度1#xff1b;如果有重复的#xff0c;左指针往右移#xff0c;那如何判断重复呢但我5分钟就写完了而且是看完题就知道怎么写这一看就知道双指针一个左一个右右指针往后移如果没有重复的长度1如果有重复的左指针往右移那如何判断重复呢这多简单Hashset的congtains方法啊所以一下子就写出来了但是效率确实不高只击败了百分之九以下是我的代码
class Solution {public int lengthOfLongestSubstring(String s) {int ans 0;int n s.length();for(int i 0;in;i){HashSetCharacter set new HashSet();set.add(s.charAt(i));int count 1;for(int j i1;jn;j){if(!set.contains(s.charAt(j))){set.add(s.charAt(j));count;}else{break;}}ans Math.max(ans, count);}return ans;}
}
看了一下题解题解就更优了一点他的右指针只需要往右移动一遍即可。
字符串abcabcbb为例找出从每一个字符开始的不包含重复字符的最长子串那么其中最长的那个字符串即为答案。 可以发现最长字串起始位置递增的时候结束位置也在递增这是因为假如我们选第k个字符为起始位置第r个字符是它的结束位置那么下次选择第k1个字符为起始位置的时候第k1到r一定是不重复的而且由于少了第k个字符那么结束位置一定大于等于r所以右指针不需要回去
但是题解和左右指针又不完全一样它用的是滑动窗口就是用一个Hashset作为一个滑动窗口里面装了左右指针之间的这一段字符如果左指针右移那么hashset就要删掉左指针之前指的那个字符如果右指针右移那么hashset就要加入右指针新指的字符了子串的长度就是右指针-左指针1以下是题解代码
class Solution {public int lengthOfLongestSubstring(String s) {int ans 0;int n s.length();for(int i 0;in;i){HashSetCharacter set new HashSet();set.add(s.charAt(i));int count 1;for(int j i1;jn;j){if(!set.contains(s.charAt(j))){set.add(s.charAt(j));count;}else{break;}}ans Math.max(ans, count);}return ans;}
}
