中国海关好神哦# Fashion - 美丽时尚
n*n
1 楼
木有用DP....
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
if (s.length() < 2) {
return s.length();
}
int maxLength = 0;
int totalLen = s.length();
int currentLen = 0;
int cStart = 0;
Map indexMap = new HashMap<>();
while((totalLen - cStart) > maxLength) {
for(int i = cStart; i < totalLen; i++) {
Character cur = s.charAt(i);
if (!indexMap.containsKey(cur)) {
currentLen++;
indexMap.put(cur, i); //update position
} else {
int position = indexMap.get(cur);
indexMap.put(cur, i); //update position
if (position < cStart || position == i){
currentLen++; // continue
} else {
if (currentLen > maxLength) {
maxLength = currentLen;
}
cStart = position + 1;
currentLen = 0;
break;
}
}
if (i == (totalLen-1)){ // corner case for last
if (currentLen > maxLength) {
maxLength = currentLen;
}
}
}
}
return maxLength;
}
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
if (s.length() < 2) {
return s.length();
}
int maxLength = 0;
int totalLen = s.length();
int currentLen = 0;
int cStart = 0;
Map
while((totalLen - cStart) > maxLength) {
for(int i = cStart; i < totalLen; i++) {
Character cur = s.charAt(i);
if (!indexMap.containsKey(cur)) {
currentLen++;
indexMap.put(cur, i); //update position
} else {
int position = indexMap.get(cur);
indexMap.put(cur, i); //update position
if (position < cStart || position == i){
currentLen++; // continue
} else {
if (currentLen > maxLength) {
maxLength = currentLen;
}
cStart = position + 1;
currentLen = 0;
break;
}
}
if (i == (totalLen-1)){ // corner case for last
if (currentLen > maxLength) {
maxLength = currentLen;
}
}
}
}
return maxLength;
}
