一：题目描述
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度
二：思路提点
- 1：找出所有子字符串然后逐一计算长度返回最长
- 2：模拟时间窗口、窗口内寻找最长字符子串
寻找所有子串会带来内存消耗以及许多无意义子串子算的问题，假设字符串为
abcde截取出来的子串为a、ab、abc、abcd、abcde、bcd、bcde、cde、de......。由该举例可以看出子串数量的倍数增加带来的内存消耗、a肯定小于ab小于abc这样的无意义比较计算
三：窗口绘图
- 1：定义两个指针分别指向无重复子串开始与结束位置
- 2：当游动遍历指针发现窗口内重复子串时计算当前子串长度
- 3：修改无重复起始指针位置到当前无重复起始指针 + 1
参照时间窗口设计的算法将会避免子串数量爆炸问题与多次无意义计算问题，当然也不用记录子串内容节约大量内存消耗。假设字符串为abcadef,起始指针位置0、遍历指针开始遍历,当遍历到第二个a时计算长度为3,调整无重复起始位置指针到第二个a位置继续遍历,结束后发现最长为4。算法核心思想就在于通过指针游动定位遍历子串位置，避免已经计算过的内容进行二次重复计算
四：代码实现
public int lengthOfLongestSubstring(String s) {
int start = 0,resultLength = 0,displament = s.length(),currentLength = 0;
Map<Character,Integer> repeatMap = new HashMap<>(displament);
for (int i = 0;i < displament;i++){
Character currentChar = s.charAt(i);
Integer returnVal = repeatMap.put(currentChar, i); //(1)
// 没有重复、重复元素坐标小于当前阅读指针位置继续进行遍历
if (returnVal == null || returnVal < start){ //(2)
continue;
}
// 当前阅读窗口内重复则变更阅读指针并计算最大的不重复子串长度
currentLength = i - start;
resultLength = Math.max(resultLength,currentLength);
start = returnVal + 1; //(3)
// 当遍历到字符串结束长度都不超过当前最大子串长度则直接返回
if (displament - start <= resultLength){ //(4)
break;
}
}
// 防止结尾那一次没有重复计算值 //(5)
currentLength = displament - start;
resultLength = Math.max(currentLength,resultLength);
return resultLength;
}
- 1: 调用Map插入数据时,如果key值重复将会返回原有value值,否则返回null。这样就可以得到重复坐标位置
- 2：当返回值为null自然没有重复可以继续遍历,当重复位置小于当期无重复起始位置自然就在非当前遍历窗口,可以忽略不计
- 3：修改无重复子串起始位置,保证修改后的遍历窗口是无重复的,继续后续的遍历
- 4：性能优化,后续的窗口遍历到结束都没有当前最长串长度大自然可以提前结束
- 5：如果遍历到最后都没有发现重复的子串那么最后一次计算就没有进行,所以需要在循环外计算一次结束位置到当前无重复指针长度
五：执行结果
