- 给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
- 分析
比如输入字符串"abcdab2aef" 。
image.png
容易想到遍历整个字符串过程中，首先可以得到第一个重复字符"a",子串指针指向第一个a。子串长度为i，j指针的差4.
image.png
当遍历指向第二个重复字符"b"的时候，子串指针指向第一个"b"。子串长度为i，j指针的差2，和上一次循环长度一致.
image.png
遍历继续到第三个重复字符"a",这时子串长度为i，j指针的差5.
image.png
但这时两指针间子串长度为2，比之前长度小，需要保留之前长度。
image.png
遍历到尾部，再没有重复字符。这时两指针差为5，和当前最大相等。
image.png
最后输出5.
分析中得出，需要有个容器，记录遍历过的字符和对应的索引，索引对应了找到下一个重复字符前子串头指针的位置。还需要一个变量记录最大子串长度。
最后，增加异常输入的边界控制。
附上OC实现。如有问题请指正：
- (int)longestSubString:(NSString *)str
{
if (!str) {
return 0;
}
if (str.length <= 1) {
return (int)str.length;
}
int ret = 0;
int i = -1; // 最长子串头的指针
NSMutableDictionary<NSString * ,NSNumber *> *window = [NSMutableDictionary dictionary];
for (int j = 0; j < str.length; j ++) {
NSString *temp = [str substringWithRange:NSMakeRange(j, 1)]; // 从字符串中取出当前字符
if ([window.allKeys containsObject:temp]) { // 字典key中包含当前字符？
int intTemp = [window objectForKey:temp].intValue; // 当前字符的上一个索引
i = MAX(intTemp, i); // 移动最长子串头的指针,到
}
ret = (int)MAX(ret, j-i);// 取遍历过程中最长的子串
[window setObject:@(j) forKey:temp]; // 存入当前字符的索引
}
return ret;
}
网友评论