leetcode复盘：3. 无重复字符的最长子串

题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

方法一：

1、利用动态规划的思想，判断每次增加一个字符时，子串长度是否需要增加；本该是用一个与字符串等长的数组来表示每个字符串作为最后一个字符时，对应的最长字串长度，但是实际上不必要，只需要用一个变量记录即可，返回最后一个字符的子串长度即可；

2、当在原有字符串末尾，新增一个字符时，判断是否需要增加最长字串长度，只需要判断新加入的字符后，前maxLen+1个，是否有相同项，若有则不需要加 （可以用反证法证明：若增加，则从末尾往前数maxlen+1个中，必须无重复字符）

3、问题转化成，已知长度的字符串中，是否有重复字符：两层遍历判断即可

4、总结：根据总体思想，逐步将问题分解，转化，最终转化成可以容易的小问题

bool IsAddSubLen(const char *s, const int post, const int maxLen) 
{
    //只需要判断新加入的字符后，前maxLen个，是否有相同项，若有则不需要加
    //判断数组s中，从post开始，倒数maxlen个数中，是否有重复元素；
    for (int i = 0; i < maxLen + 1; i++) {
        for (int j = i + 1; j < maxLen + 1; j++) {
            if (s[post - i] == s[post - j]) {
                return false;
            }
        }
    }
    return true;
}
int lengthOfLongestSubstring(char * s)
{
    //逐个加入数字
    int sLen = strlen(s);
    if (sLen <= 1) {
        return sLen;
    }
    int maxLen = 1;
    for(int i = 1; i < sLen; i++) {
        //判断第i个数添加后，最长子串是否需要刷新
        if (IsAddSubLen(s, i, maxLen) ) {
            maxLen++;
        } 
    }
    return maxLen;
}

运行结果