LeetCode -- Longest Substring Without Repeating Characters

前言

可以这样学习算法：
Mac有神器CodeRunner，可是只能运行不能调试。
所以我用XCode的新建OSX Application下的Command Line Tool项目：
然后 打断点！！

题目

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

提示 Hash Table Two pointers

思路：

找到 最长的 没有重复子母的 字符串的 长度！

LeetCode上给了参考答案：
我把它写到了XCode中：

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int lengthOfLongestSubstring(string s) {
    int n = (int)s.length();
    int i = 0, j = 0;
    int maxLen = 0;
    bool exist[256] = { false };
    while (j < n) {
        if (exist[s[j]]) {
            maxLen = max(maxLen, j-i);
            while (s[i] != s[j]) {
                exist[s[i]] = false;
                i++;
            }
            i++;
            j++;
        } else {
            exist[s[j]] = true;
            j++;
        }
    }
    maxLen = max(maxLen, n-i);
    return maxLen;
}

int main(int argc, const char * argv[]) {
    string s = "abcabcbb";
    int length = lengthOfLongestSubstring(s);
    printf("length: %d\n", length);
    return 0;
}

说明：

1. exist[]很精髓，字母放入后，下标是该字母在ASCII码的值。 ASCII码长度只有128位，但是它初始256位，原因暂不清楚。
2. 外层while在改变j的值，j最多从0改变到n(n为字符串的长度)，内层while在改变i的值，同样的，i最多从0改变到n(n为字符串的长度)。所以加起来，时间复杂度为O(2*N)，也就是O(N)。
3. 在循环体之外，还要写上，maxLen = max(maxLen, n-i)。这是为什么呢? 因为可能最后一次检查的时候，j知道走到字符串末尾都没有遇到重复字符。而while循环体中找到的最长不重复子串只是在j遇到重复字符时才进行的。