题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成（from LeetCode）
这道题比较简单，只要去重，无脑联想集合总没有错，因此使用数据结构HashSet。顺便复习了代码单元和码点的概念，分别用方法一（lengthOfLongestSubstring1）和方法二（lengthOfLongestSubstring2）而完成，但是时间复杂度是O(n²)，因此思考别的算法。
参考此题的算法介绍，可以采用滑动窗口算法，方法三（lengthOfLongestSubstring3）将时间复杂度降为O(n)，只遍历字符串一次。因为字符集是ASCII，取值在[0,128)之间，因此还有更简便的算法，之后再写。
通过本题，可以延伸思考：
1.码点和代码单元的区别。
2.集合Set的用法。
3.HashSet，LinkedHashSet，TreeSet应用场景的不同。
4.滑动窗口在算法中的应用场景条件。
5.Java流操作对于代码的简化。
class Solution {
public int lengthOfLongestSubstring1(String s) {
HashSet<Character> set=new HashSet<>();
int sub=0;
for(int i=0;i<s.length();i++){
for(int j=i;j<s.length();j++){
if(set.contains(s.charAt(j))){
if(set.size()>sub){
sub=set.size();
}
set.clear();
break;
}else set.add(s.charAt(j));
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
public int lengthOfLongestSubstring2(String s) {
HashSet<Integer> set=new HashSet<>();
int sub=0;
int[] codePoints=s.codePoints().toArray();
for(int i=0;i<codePoints.length;i++){
for(int j=i;j<codePoints.length;j++){
if(set.contains(codePoints[j])){
if(set.size()>sub){
sub=set.size();
}
set.clear();
break;
}else set.add(codePoints[j]);
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
public int lengthOfLongestSubstring3(String s) {
HashSet<Character> set=new HashSet<>();
int sub=0;
int right=-1;
for(int i=0;i<s.length();i++){
if(i>0) set.remove(s.charAt(i-1));
while(right<(s.length()-1)&&!(set.contains(s.charAt(right+1)))){
set.add(s.charAt(right+1));
right++;
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
}//wriiten by lvyimeng
public int lengthOfLongestSubstring1(String s) {
HashSet<Character> set=new HashSet<>();
int sub=0;
for(int i=0;i<s.length();i++){
for(int j=i;j<s.length();j++){
if(set.contains(s.charAt(j))){
if(set.size()>sub){
sub=set.size();
}
set.clear();
break;
}else set.add(s.charAt(j));
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
public int lengthOfLongestSubstring2(String s) {
HashSet<Integer> set=new HashSet<>();
int sub=0;
int[] codePoints=s.codePoints().toArray();
for(int i=0;i<codePoints.length;i++){
for(int j=i;j<codePoints.length;j++){
if(set.contains(codePoints[j])){
if(set.size()>sub){
sub=set.size();
}
set.clear();
break;
}else set.add(codePoints[j]);
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
public int lengthOfLongestSubstring3(String s) {
HashSet<Character> set=new HashSet<>();
int sub=0;
int right=-1;
for(int i=0;i<s.length();i++){
if(i>0) set.remove(s.charAt(i-1));
while(right<(s.length()-1)&&!(set.contains(s.charAt(right+1)))){
set.add(s.charAt(right+1));
right++;
}
if(set.size()>sub) sub=set.size();
}
return sub;
}
}//wriiten by lvyimeng
文章评论