【iOS每日算法】无重复字符的最长子串（滑动窗口）：给定一个字符

题目：

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

考察点：

• 这是一道LeetCode上非常基础的一道算法题。考察点滑动窗口。

解法：

一、暴力查找（我最开始想到的解法）

• 因为是查找最长不含重复字符的最长子串。我们就从最长长度n开始查找这个长度的字符串中是否有重复字符，如果没有重复字符return。如果有重复字符则查找n-1长的子串中是否有重复字符。
• 时间复杂度就不写了。。循环n次，还要查询重复n次。。总之就是很复杂

- (NSInteger)checkTheString:(NSString *)content {
    NSInteger length = content.length;
    for (NSInteger i = length; i > 0; i--) {
        // i为子串长度
        for (NSInteger j = 0; j + i <= length; j++) {
            // 从0开始截取长度为i的子串
            NSRange range = NSMakeRange(j, i);
            NSString *rangeString = [content substringWithRange:range];
            NSMutableDictionary *letterDic = [[NSMutableDictionary alloc]init];
            // 循环遍历子串，如果有重复的字符结束循环，移动子串位置，如果没有重复字符return当前子串长度
            for (NSInteger c = 0; c < rangeString.length; c++) {
                NSRange letterRange = NSMakeRange(c, 1);
                NSString *letter = [rangeString substringWithRange:letterRange];
                if([[letterDic allKeys] containsObject:letter]) {
                    break;
                } else {
                    [letterDic setValue:@"1" forKey:letter];
                }
                if(c == rangeString.length - 1) {
                    return i;
                }
            }
        }
    }
    return 1;
}

二、滑动窗口法

• 我们使用两个指针表示字符串中的某个子串（的左右边界）
• 在每次循环检查向右移动右指针，检查右指针指向的字符在之前是否有重复
• 如无重复，记录下长度并将该字符的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];
        // 判断是否含有滑动加入的字符
        if([[checkedDict allKeys]containsObject:letter]) {
            // 如果有将记录子串起始位置的start移动到该字符之前出现的位置的下一个位置
            // 相当于把左边指针向右拉，直到不包含当前遍历的字符，这样这个子串中就没有重复字符了
            start = [[checkedDict objectForKey:letter] integerValue] + 1;
            NSInteger tempLength = i - start + 1;
            // 毕竟子串长度，取最长的
            if(tempLength > maxLength) {
                maxLength = tempLength;
            }
        }
        // 更新子串中该字符位置
        [checkedDict setObject:@(i) forKey:letter];
    }
    return maxLength;
}

总结

• 学习了滑动窗口模型

思考

• 这个题做完，感觉还是没有摸到算法的门路。是因为经验不够？还是思路太死板？总觉得算法这种东西，不应该去靠经验积累去成长，而是思维的进化。觉得自己好笨。。