这是一个创建于 2462 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
Given a string, find the length of the longest substring without repeating characters.
public int lengthOfLongestSubstring(String s) {
int longest=Integer.MIN_VALUE;
for(int i=0;i<s.length();i++){
int k=i;
while(++k<=s.length()){
String sub=s.substring(i,k);
longest=sub.length()>longest?sub.length():longest;
// 子串到结尾或者子串后面的那个字符包含在子串里，结束循环
if(k==s.length()||sub.contains(s.substring(k,k+1) )){
break;
}
}
}
return longest==Integer.MIN_VALUE?s.length():longest;
}
 |
1
snowonion 2018-03-24 12:20:11 +08:00
尝试证明正确性：
当执行到 `String sub=s.substring(i,k);` 时，`s.substring(i,k)` 总是无重复字符的，那么只要 `s.substring(i,k)` 不含有 `s.charAt(k)`，`s.substring(i,k+1)` 就是无重复字符的。 楼主可以再试试证贪心算法做这题的正确性。 |
Select Language