例如,给定字符串str为abcabcbb
不含有重复字符的最长子串为abc
首先分析下
1. 要确定一个字串,就要确定这个子串的起止位置.
2. 为确定字串起始位置,最好方式就是使用2个分别代表起止位置的指针.
3. 为判断字符是否重复,还需要一个记录遍历过字符的数据结构,并存储该字符下标,这个数据结构选为HashMap比较合适.
4. 遍历字符串,当有字符重复时,移动起始位置指针,从指针位置开始到当前遍历下标位置就是一个新的无重复字符的字串.
5. 重新记录重复元素的下标.
这个要查找的最长字串便称作滑动窗口,时间复杂度为O(n),下面用几个图说明下.
1.起始状态,滑动窗口的起始指针start和字符串遍历指针i都指向0;
2.移动指针i,并将遍历过元素记录到HashMap中,便于比对.
3.当指针i移动到第二个[a]元素时,判断出元素重复;
为判断出最长字串,需要对比并记录此时最大滑动窗口;
需要重新调整滑动窗口的起始指针start,调整HashMap中元素下标值;继续遍历.
4.遍历结束时,记录下的最大滑动窗口位置就是求得的无重复字符的最长字串.
通过上述遍历过程可以发现,滑动窗口也是快慢指针的另一种表现形式.对于这种查找范围的情况,可以思考下是否适合应用场景.
附上代码:
代码语言：javascript复制 String stringOfLongestSubstring(String string) {
int start = 0;
char[] chars = string.toCharArray();
String lastString = "";
Map<Character, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < chars.length; i ) {
char c = chars[i];
Integer existCharIndex = map.get(c);
if (null != existCharIndex && existCharIndex >= start) {
// 长度比较
String tmp = string.substring(start, i);
if (tmp.length() > lastString.length()) {
lastString = tmp;
}
// 窗口起始位置移动到重复字符的下一位
start = existCharIndex 1;
map.put(c, i);
} else {
map.put(c, i);
sb.append(c);
}
}
String tmp = string.substring(start);
if (tmp.length() > lastString.length()) {
lastString = tmp;
}
return lastString;
}
