昨天被网易二面投屏算法虐了一番，痛定思痛，每日一道算法题。下面来看看这道算法题：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度和字符。
输入: "abcabcbb"
输出: 3,abc,bca,cab
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
这道题其实是一道经典的滑动窗口应用的题目，但是上网查了一下，结果很多的OC算法代码其实都是错误的，例如点击最多的这位(【iOS每日算法】无重复字符的最长子串（滑动窗口）：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 - 简书)，下面先上代码：
`- (NSInteger)checkTheStringScan:(NSString *)content {
//abdfhabcojdsnagjsu
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];
// 判断是否含有滑动加入的字符
if([[checkedDict allKeys]containsObject:letter]) {
// 如果有将记录子串起始位置的start移动到该字符之前出现的位置的下一个位置
// 相当于把左边指针向右拉，直到不包含当前遍历的字符，这样这个子串中就没有重复字符了
start = [[checkedDict objectForKey:letter] integerValue] + 1;
}
//注意这里必须也是网上常常错误的地方,每个i即右指针都需要经过计算得到当前子串长度
NSInteger tempLength = i - start + 1;
// 取最长的子串
if(tempLength >=maxLength) {
maxLength = tempLength;
NSLog(@"%@",[content substringWithRange:NSMakeRange(start, maxLength)]);
}
// 更新子串中该字符位置
[checkedDict setObject:@(i) forKey:letter];
}
return maxLength;
}`
实现思路的话，主要就是通过for循环，以i为右指针开始滑动，当遇到相同字符的时候，对两者后面的一个进行位置i的记录（这里使用了字典的key来实现的，也可以使用Set实现，唯一性保证），记录完相同字符后，左指针start记录相同字符前者的后一个字符位置，取左右指针的中间长度tempLength计算方式：i-start+1,记录完成后遍历自校tempLength的最大长度即最长不重复子串的长度，start即最长子串起始位置，得出最长子串内容如下：
`2021-07-15 15:40:19.677857+0800 arithmeticTest[19183:2180250] fhabcojdsn
2021-07-15 15:40:19.678016+0800 arithmeticTest[19183:2180250] 10`
第二种更简单的NSMutableSet实现的滑动窗口，直接代码：
`- (void)checkTheStringScanTwo {
NSString *str = @"abdfhabcojdsnagjsu";
NSMutableSet *set = [NSMutableSet new];
long n = str.length;
//ans:最长子串长度,j:右指针,i:左指针
int ans = 0, i = 0, j = 0 ,index = 0;
while (i<n && j<n) {
//和上一个算法相反,判断不包含则添加更合理
if (![set containsObject:[str substringWithRange:NSMakeRange(j,1)]]) {
//右指针滑动
[set addObject:[str substringWithRange:NSMakeRange(j++, 1)]];
//取指针区间内最大值
if (j - i > ans) {
ans = j - i;
index = i;
}
}else{
//出现相同字符则删除前一个,并i++,左指针右偏移一
[set removeObject:[str substringWithRange:NSMakeRange(i++, 1)]];
}
}
NSLog(@"%@",[str substringWithRange:NSMakeRange(index, ans)]);
}`
平时多积累，面试别紧张，冷静思考，其实都不难。
