Question

java 实现 一个字符串中不重复最长子串

public static void longestNodupSubstring(String string) {
int len = string.length();
if(len > 0){
Map<Character,Integer> cursor = new HashMap<Character,Integer>();
cursor.put(string.charAt(0),0);
int[] lengthAt = new int[string.length()];
lengthAt[0]=1;
int max = 0 ;
for(int i = 1 ; i < len;i++){
char c =string.charAt(i);
if(cursor.containsKey(c)){
lengthAt[i] = Math.min(lengthAt[i-1]+1, i-cursor.get(c));
}else {
lengthAt[i] = lengthAt[i-1]+1;
}
max = Math.max(max, lengthAt[i]);
cursor.put(c, i);
}
for(int i=0;i<len;i++){
if(max == lengthAt[i]){
System.out.println(string.substring(i-max+1, i+1));
}
}
}
}

}
不太理解lengthAt[i]和max的取值，能仔细讲讲这个程序的执行过程

Answer 1

这个函数的目的是求最长不重复子串，所谓不重复子串是指由某个字符串中相邻的N个字符组成，这个N内所有字符都是不重复的，最长是指这个N最大。如字符串"abcdefghiud",最长的不重复的子串为"abcdefghiu"
cursor里面存放字符的在字符串中的位置
lengAt[i]存放以字符string.charAt(i)结尾的最长子字符串的长度
max的目的就是确定这个最长，因为最开始可能找到的子串比以后找到的子串短，所以用max比较

Answer 2

实现思路就是先拿第一个字符和第二个字符比较，不一样的话，取到这两个字符，之后和第三个比较，直到出现重复的保存下来（多次循环，取出最长的一个）。
public static void longestNodupSubstring(String string) {
int len = string.length();
if(len > 0){
Map<Character,Integer> cursor = new HashMap<Character,Integer>();
cursor.put(string.charAt(0),0);
int[] lengthAt = new int[string.length()];
lengthAt[0]=1;
int max = 0 ;
for(int i = 1 ; i < len;i++){
char c =string.charAt(i);
if(cursor.containsKey(c)){
lengthAt[i] = Math.min(lengthAt[i-1]+1, i-cursor.get(c));
}else {
lengthAt[i] = lengthAt[i-1]+1;
}
max = Math.max(max, lengthAt[i]);
cursor.put(c, i);
}
for(int i=0;i<len;i++){
if(max == lengthAt[i]){
System.out.println(string.substring(i-max+1, i+1));
}
}
}
}

}