无重复字符的最长子串

题目

这是leetcode上的第三题

题目解析

本题可以利用滑动窗口的思想来解决，题目要求给我们一个字符串让我们求出其中没有重复字符的最长子串，我们可以先简单分析下，以题目中的实例一为例：

我们可以设立两层循环，外层循环对字符串进行整体遍历—代表子串的起始点i，内层循环从当前起始点开始往后遍历，并且将每一个当前遇到的字符存入哈希集合当中，根据哈希表的特点我们可以很快地找出哈希表中是否存在某个字符，当不存在的时候内存循环结束，同时在内层循环中我们还是需要维护一个右边界的指针r，每循环一次内层循环就加一，当内层循环结束时，就代表从外层循环选择的左边界i到内层循环维护的右边界指针r这个区间的字符串为当前起始点的无重复字符的最长子串，这时与最大值max进行比较赋值，当整个循环完成，这个max就是最大的长度。

具体代码

func lengthOfLongestSubstring(s string) int {
    //存储当前最长不重复子串，用来查询下个字符是否存在
    maps := map[byte]int{}
    //r是子串的右置针，这里还没有还是移动所以初始化为-1
    //max记录最大的子串的长度
    r,max := -1,0
    //从头开始遍历字符串
    for i:=0;i<len(s);i++{
        //当每一次外层循环结束就代表i++也就是待遍历子串的左边界加一，所以这个时候我们需要讲maps中
        //的最左字符删除
        if i>0{
            delete(maps, s[i-1])
        }
        for r<len(s)-1&&maps[s[r+1]]==0{
            maps[s[r+1]] = 1
            r++
        }
        if max<r-i+1{
            max = r-i+1
        }
    }
    return max
}