查找最长子串的长度（不重复字符）

描述：

给定一个字符串，找到最长子串的长度，而不重复字符。

例子：

给定"abcabcbb"的答案是"abc"，长度是3。

给定"bbbbb"的答案是"b"，长度为1。

给定"pwwkew"的答案是"wke","kew"，长度为3。

暴力法,最好想,先记录一个最大值,挨个遍历每个字符,找出重复的字符就从下一个字符接着遍历,更新最大值,最后遍历完成后,最大值就是最长的子串长度了. 暴力法的时间复杂度是O(n^2).

/// 暴力枚举,
void fun1() {
    
    NSString * s = @"abcdafhgh";
    // 把单个字符放到数组里
    NSMutableArray * array = [NSMutableArray array];
    for (int i =0 ; i<s.length; i++) {
        NSString * temp = [s substringWithRange:NSMakeRange(i, 1)];
        [array addObject:temp];
    }
    
    int maxLength = 0;
    for (int i=0; i<array.count; i++) {
        // 用字典判断是否重复
        NSMutableDictionary * dic = [[NSMutableDictionary alloc] init];
        int j=i;
        for (; j<array.count; j++) {
            
            NSString * s = dic[ array[j] ] ;
            if (s==nil) {
                dic[ array[j] ] = @"1";
                continue;
            }
            break;
        }
        // 到这说明一件重复了,记录下最长的数据
        maxLength = MAX(maxLength, dic.count);
        NSLog(@"长度为 : %d %@",dic.count,dic);
        // j==array.count,说明遍历到最后了,这个值就是最大值了
        if (j==array.count) {
            break;
        }
    }
    NSLog(@"最大长度为 : %d",maxLength);
    
}

跳步处理,记录一个最大值,挨个遍历每个字符,找出重复的字符就从重复字符的下一个开始遍历, 

来个例子就懂了, 比如"axhchg",从a开始,遇到了第二个h,发现了重复, 暴力法的解决就是记录最大值"axhc",然后下一个从"x"往下找.

跳步处理,发现了重复,找到那个重复元素第一次出现的位置,然后从重复元素的下一个开始,在例子中就是从"c"开始处理,把前面的给跳过了. 同时还做了一个优化,就是子循环如果到字符串结尾了,说明最长的值已经找到了,可以直接break了. 这样处理后,跳步法的时间复杂度就是O(n)了.

/// 跳步处理
void fun2() {
    
    NSString * s = @"abcdafhgh";
    // 把单个字符放到数组里
    NSMutableArray * array = [NSMutableArray array];
    for (int i =0 ; i<s.length; i++) {
        NSString * temp = [s substringWithRange:NSMakeRange(i, 1)];
        [array addObject:temp];
    }
    
    int maxLength = 0;
    NSNumber * charIndex = nil;
    for (int i=0; i<array.count; i++) {
            
        NSMutableDictionary * dic = [[NSMutableDictionary alloc] init];
        int j = i;
        for (; j<array.count; j++) {
            
            charIndex = dic[ array[j] ] ;
            if (charIndex==nil) {
                // 用当前下标的值记录到字典中,
                dic[ array[j] ] = @(j);
                continue;
            }
            // 说明发现重复了
            break;
        }
        
        if (charIndex.intValue > 0) {
            i = [charIndex  intValue];
        }
        // 到这说明一件重复了,记录下最长的数据
        maxLength = MAX(maxLength, dic.count);
        NSLog(@"长度为 : %d ",dic.count);
        // j==array.count,说明遍历到最后了,这个值就是最大值了
        if (j==array.count) {
            break;
        }
        
    }
    NSLog(@"最大长度为 : %d",maxLength);
    
    
}

最后测试一下效果: 

在都执行50000次的情况下,方法2明显优于方法1.