例如,给定字符串str为abcabcbb
不含有重复字符的最长子串为abc
首先分析下
1. 要确定一个字串,就要确定这个子串的起止位置.
2....为确定字串起始位置,最好方式就是使用2个分别代表起止位置的指针.
3. 为判断字符是否重复,还需要一个记录遍历过字符的数据结构,并存储该字符下标,这个数据结构选为HashMap比较合适.
4....遍历字符串,当有字符重复时,移动起始位置指针,从指针位置开始到当前遍历下标位置就是一个新的无重复字符的字串.
5. 重新记录重复元素的下标....这个要查找的最长字串便称作滑动窗口,时间复杂度为O(n),下面用几个图说明下.
1.起始状态,滑动窗口的起始指针start和字符串遍历指针i都指向0;
2.移动指针i,并将遍历过元素记录到HashMap...中,便于比对.
3.当指针i移动到第二个[a]元素时,判断出元素重复;
为判断出最长字串,需要对比并记录此时最大滑动窗口;
需要重新调整滑动窗口的起始指针start,调整HashMap中元素下标值;继续遍历