[LeetCode] 3. 无重复字符的最长子串

[Animenzzzz]

题目描述：

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路：这题做了好久，提交了很多次。看了网上的解题思路。使用哈希表建立下标和值的映射，使用 滑动窗口 的解题思想。begin和end之间组成的字符串就是无重复字符的串。每遇到新值，end就后移，若遇到重复，则删除此字符在哈希表的映射，同时begin开始往后移。

C解题：

struct HashMap {
    int value;
    int index;
    UT_hash_handle hh;
};
int themax(int,int);
int themax(int a,int b){
    if(a>b) return a;
    else return b;
}
int lengthOfLongestSubstring(char * s){
    if(strlen(s) == 1) return 1;
    struct HashMap *hashtmp = NULL,*hashmap = NULL;
    int begin = 0,end = 0;
    int max_length = 0;
    while (end < strlen(s) && begin<strlen(s))
    {
        int tt = s[end] - '0';
        HASH_FIND_INT(hashmap,&tt,hashtmp);
        if (hashtmp)
        {
            tt = s[begin] - '0';
            HASH_FIND_INT(hashmap,&tt,hashtmp);
            HASH_DEL(hashmap,hashtmp);
            begin++;
        }else
        {
            hashtmp = (struct HashMap *)malloc(sizeof(struct HashMap));
            hashtmp->value = s[end] - '0';
            hashtmp->index = end;
            HASH_ADD_INT(hashmap,value,hashtmp);
            max_length = themax(max_length,end-begin+1);
            end++;
        }
    }
    return max_length;
}