LeetCode第3题: lengthOfLongestSubs

上一题：LeetCode第2题:add-two-numbers(C语言）

字典方法
思路：
1、本题可以这样理解，有两种情况：
如果输入的字符数组s有两个重复字符，比如s = "abcabcbb"中两个相同字符“a”的子串，其中一个最长无重复子串为"abc"，即s[0] - s[2]，这时只要能记录下最长无重复子串的起止位置下标，即"a"对应的下标 i = 0，当顺序遍历s数组到下标j = 3时，查看字典发现字典中已经存在了上一个字符"a"位在s[0]，所以最长的结果为"c"对应的下标 j = 2即可；
如果s的最长无重复子串不是位于两个重复字符的之间，比如s = "abcabcde"，明显，最长无重复子串为"abcde"，即s[3] - s[7]，这时就需要记录上次的计算的起始位置last_index = 2，然后用下标 j = 7 减去last_index = 5。
2、同LeetCode第1题:two-sum(C语言）一样，创建字典map数组，用于快速定位目标字符在字符串数组中的索引 。我们知道字符的ASCII码值位于0-128区间，为简单起见，初始化map数组大小为128。map数组以数组下标为要找的字符串，对应数组的值为该下标在nums数组中的下标位置，例如map['a'] = 5，即在输入的字符串数组s中，字符'a'在s中的上次出现的下标为5。为了防止map数组初始化的时候数组元素随机赋值，需要用到calloc函数，将map的元素值均初始化为0。
为了防止输入字符存在空字符（空字符的ASCII码值=0），对所有的输入字符保存字典索引的时候，对应的保存对应的下标+1。
3、遍历s数组，对于s中的每一个数组元素字符cur，首先判断字符c是否存在过，如果存在，则map[cur]的值大于0，而且cur上次出现的索引（map[cur] - 1）比last_index大时，将last_index更新为cur上次出现的索引（map[cur] - 1）+ 1 即last_index = map[cur]。

int lengthOfLongestSubstring(char* s) {
    int length = strlen(s);
    int max = 0;
    int last_index = 0;
    
    int *map = (int *)calloc(128, sizeof(int));
    
    for(int i = 0; i < length; i++){
        char cur = s[i];
        if(map[cur] && map[cur] - 1 >= last_index){
            last_index = map[cur];
        }
        map[cur] = i + 1;  //为了防止输入字符存在空字符（空字符的ASCII码值=0），对所有的输入字符保存字典索引的时候，对应的保存对应的下标+1
        if(i - last_index + 1> max){
            max = i - last_index + 1;
        }  
    }
    return max;
}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。

下一题：LeetCode第4题:findMedianSortedArrays(C语言）