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

3 无重复字符的最长子串

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

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

思路：滑动窗口法

想象一个窗口，当abc进入窗口后，无重复字符，目前最长子串长度为3.当后一个a进入后，变成了abca出现了重复字符a。所以要将窗口进行滑动，以满足要求。如何滑动？将队列左边的元素移除即可。一直维持这样的队列，直到找出最长长度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int lengthOfLongestSubstring(String s) {
    if(s.length() == 0)
        return 0;
    //哈希表的value值为key值上一次出现过的位置(s中的索引)
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    //max用来储存不含重复字符的最长子串长度
    int max = 0;
    //left用来储存滑动窗口的左端
    int left = 0;
    for(int i = 0; i < s.length(); i++){
        //如果map中出现过s[i]，则再将s[i]加入时会出现重复字符，因此需要进行窗口滑动，即更新left
        if(map.containsKey(s.charAt(i)))
            //将left更新为之前出现过的与s[i]相同的字符的下一个位置，即将那个相同字符滑出窗口
            //例子abba可以说明为何需要和left取最大，当填入第二个a时，left在索引为2处，但第1个a的下一个位置为索引为1处。
            left = Math.max(left, map.get(s.charAt(i))+ 1);
        //不管s[i]是否出现过，都将它put进哈希表。
        //如果map中曾经有s[i]，这一操作相当于把其value值更新
        map.put(s.charAt(i),i);
        //更新最长长度max值
        max = Math.max(max,i-left+1);
    }
    return max;
}

滑动窗口法题目汇总