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

什么是滑动窗口？

其实就是一个队列，比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)。

Java解决方法

需要一种数据结构来判断是否有重复字符：HashSet。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> ss = new HashSet<Character>();
        int slen = s.length();
        int length = 0;
        int maxLength = 0;
        for(int i = 0; i < slen; i++)
        {
            //退出队列中的一个元素
            if(i != 0)
            {
                ss.remove(s.charAt(i - 1));
            }
            //向队列中加入元素,加入时HashSet会自动判断有无重复
            while(length < slen  && ss.add(s.charAt(length)))
            {
                length++;
            }
            if(maxLength < length - i)
            {
                maxLength = length - i;
            }
        }
        return maxLength;
    }
}

C语言解决方法

bool haveSame(char *ss, int start, int end, char c)
{
    int i = start;
    if(end == 0)
    {
        return true;
    }
    while(i < end && ss[i] != c)
    {
        i++;
    }
    if(i >= end)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int lengthOfLongestSubstring(char * s){
    char *ss = NULL;
    int len;
    len = strlen(s);
    ss = (char *)malloc(len * sizeof(char));
    int length = 0;
    int maxLength = 0;
    for(int i = 0; i < len; i++)
    {
        //向队列中加入元素,加入时HashSet会自动判断有无重复
        while(length < len  && haveSame(ss, i, length, s[length]))
        {
            ss[length] = s[length];
            length++;
        }
        if(maxLength < length - i)
        {
            maxLength = length - i;
        }
    }
    return maxLength;
}