给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
-(NSInteger )getAlgfirstString:(NSString *)content
{
// NSString *content = @"afdsdssscscdv";
NSInteger lenth = content.length;
for (NSInteger i = lenth; i > 0; i--) {
// i 为子串长度
for (NSInteger j = 0; j+i <= lenth; j++) {
// 从0开始截取长度为i的子串
NSRange range = NSMakeRange(j, i);
NSString *rangeString = [content substringWithRange:range];
NSMutableDictionary *letterDic = [[NSMutableDictionary alloc]init];
NSLog(@"j == %ld, i == %ld,rangeString = %@",j,i,rangeString);
// 循环遍历子串，如果有重复的字符串结束循环，移动子串位置，如果没有重复字符return当前子串长度
for (NSInteger c = 0; c < rangeString.length; c++) {
NSRange letterRange = NSMakeRange(c, 1);
NSString *letter = [rangeString substringWithRange:letterRange];
NSLog(@"letter == %@",letter);
if ([[letterDic allKeys]containsObject:letter]) {
NSLog(@"letterDic == %@",letterDic);
break;
}else{
[letterDic setValue:@"1" forKey:letter];
}
if (c == rangeString.length - 1) {
NSLog(@"i == %ld",i);
return i;
}
}
}
}
}
2020-10-20 17:22:20.727952+0800 ThreadDemo[2137:188852] j == 0, i == 8,rangeString = wshdtbsd
2020-10-20 17:22:20.728094+0800 ThreadDemo[2137:188852] letter == w
2020-10-20 17:22:20.728217+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.728311+0800 ThreadDemo[2137:188852] letter == h
2020-10-20 17:22:20.728417+0800 ThreadDemo[2137:188852] letter == d
2020-10-20 17:22:20.728506+0800 ThreadDemo[2137:188852] letter == t
2020-10-20 17:22:20.728601+0800 ThreadDemo[2137:188852] letter == b
2020-10-20 17:22:20.728695+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.728873+0800 ThreadDemo[2137:188852] letterDic == {
b = 1;
d = 1;
h = 1;
s = 1;
t = 1;
w = 1;
}
2020-10-20 17:22:20.729276+0800 ThreadDemo[2137:188852] j == 0, i == 7,rangeString = wshdtbs
2020-10-20 17:22:20.729585+0800 ThreadDemo[2137:188852] letter == w
2020-10-20 17:22:20.729904+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.730240+0800 ThreadDemo[2137:188852] letter == h
2020-10-20 17:22:20.730505+0800 ThreadDemo[2137:188852] letter == d
2020-10-20 17:22:20.730799+0800 ThreadDemo[2137:188852] letter == t
2020-10-20 17:22:20.731096+0800 ThreadDemo[2137:188852] letter == b
2020-10-20 17:22:20.731363+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.731674+0800 ThreadDemo[2137:188852] letterDic == {
b = 1;
d = 1;
h = 1;
s = 1;
t = 1;
w = 1;
}
2020-10-20 17:22:20.731980+0800 ThreadDemo[2137:188852] j == 1, i == 7,rangeString = shdtbsd
2020-10-20 17:22:20.737182+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.737297+0800 ThreadDemo[2137:188852] letter == h
2020-10-20 17:22:20.737400+0800 ThreadDemo[2137:188852] letter == d
2020-10-20 17:22:20.737495+0800 ThreadDemo[2137:188852] letter == t
2020-10-20 17:22:20.737594+0800 ThreadDemo[2137:188852] letter == b
2020-10-20 17:22:20.737686+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.737798+0800 ThreadDemo[2137:188852] letterDic == {
b = 1;
d = 1;
h = 1;
s = 1;
t = 1;
}
2020-10-20 17:22:20.737897+0800 ThreadDemo[2137:188852] j == 0, i == 6,rangeString = wshdtb
2020-10-20 17:22:20.738115+0800 ThreadDemo[2137:188852] letter == w
2020-10-20 17:22:20.738385+0800 ThreadDemo[2137:188852] letter == s
2020-10-20 17:22:20.738655+0800 ThreadDemo[2137:188852] letter == h
2020-10-20 17:22:20.738961+0800 ThreadDemo[2137:188852] letter == d
2020-10-20 17:22:20.739270+0800 ThreadDemo[2137:188852] letter == t
2020-10-20 17:22:20.739548+0800 ThreadDemo[2137:188852] letter == b
2020-10-20 17:22:20.739844+0800 ThreadDemo[2137:188852] i == 6
2020-10-20 17:22:20.740179+0800 ThreadDemo[2137:188852] 非重复长度- 6
二、滑动窗口法
- 我们使用两个指针表示字符串中的某个子串（的左右边界）
- 在每次循环检查向右移动右指针，检查右指针指向的字符在之前是否有重复
- 如无重复，记录下长度并将该字符的index为值，该字符为key存入字典中。
- 如有重复，则将左指针，指向子串中上一个该字符的下一个字符（这样最新的左指针到右指针就没有重复字符）
- 同时更新该字符在字典中的位置，将该字符的index为值，该字符为key存入字典中。
- 计算次字符串长度，并与之前无重复字符串长度比对，如果本次更长，则更新最长长度，最后return
- 时间复杂度O(n)只需循环一次字符串
- (NSInteger)checkTheStringScan:(NSString *)content {
NSInteger length = content.length;
// 记录已经遍历过的字符所在位置的字典
NSMutableDictionary *checkedDict = [[NSMutableDictionary alloc]init];
NSInteger maxLength = 0;
//记录子串起始位置的指针
NSInteger start = 0;
// 循环字符串 i 为右边指针，不断向右移动，像一个往右划的窗口
for (NSInteger i = 0; i < length ; i++) {
NSRange letterRange = NSMakeRange(i, 1);
NSString *letter = [content substringWithRange:letterRange];
NSLog(@"letter == %@ ",letter);
// 判断是否含有滑动加入的字符
if([[checkedDict allKeys]containsObject:letter]) {
// 如果有将记录子串起始位置的start移动到该字符之前出现的位置的下一个位置
// 相当于把左边指针向右拉，直到不包含当前遍历的字符，这样这个子串中就没有重复字符了
NSLog(@"checkedDict == %@,[checkedDict allKeys] = %@",checkedDict,[checkedDict allKeys]);
start = [[checkedDict objectForKey:letter] integerValue] + 1;
NSInteger tempLength = i - start + 1;
NSLog(@"start == %ld ,tempLength = %ld",start,tempLength);
// 毕竟子串长度，取最长的
if(tempLength > maxLength) {
maxLength = tempLength;
NSLog(@"maxLength == %ld ",maxLength);
}
}
// 更新子串中该字符位置
[checkedDict setObject:@(i) forKey:letter];
}
return maxLength;
}
2020-10-20 17:48:58.979685+0800 ThreadDemo[2241:204126] letter == w
2020-10-20 17:48:58.979819+0800 ThreadDemo[2241:204126] letter == s
2020-10-20 17:48:58.979934+0800 ThreadDemo[2241:204126] letter == h
2020-10-20 17:48:58.980096+0800 ThreadDemo[2241:204126] letter == d
2020-10-20 17:48:58.980215+0800 ThreadDemo[2241:204126] letter == t
2020-10-20 17:48:58.980407+0800 ThreadDemo[2241:204126] letter == b
2020-10-20 17:48:58.980667+0800 ThreadDemo[2241:204126] letter == s
2020-10-20 17:48:58.981013+0800 ThreadDemo[2241:204126] checkedDict == {
b = 5;
d = 3;
h = 2;
s = 1;
t = 4;
w = 0;
},[checkedDict allKeys] = (
d,
w,
b,
s,
h,
t
)
2020-10-20 17:48:58.981414+0800 ThreadDemo[2241:204126] start == 2 ,tempLength = 5
2020-10-20 17:48:58.981848+0800 ThreadDemo[2241:204126] maxLength == 5
2020-10-20 17:48:58.981949+0800 ThreadDemo[2241:204126] letter == d
2020-10-20 17:48:58.982339+0800 ThreadDemo[2241:204126] checkedDict == {
b = 5;
d = 3;
h = 2;
s = 6;
t = 4;
w = 0;
},[checkedDict allKeys] = (
d,
w,
b,
s,
h,
t
)
2020-10-20 17:48:58.982739+0800 ThreadDemo[2241:204126] start == 4 ,tempLength = 4
2020-10-20 17:48:58.983180+0800 ThreadDemo[2241:204126] 非重复长度- 5
参考简书
网友评论