leetcode-longest-substring-without-repeating-characters

发表于   |  

题目大意

　　https://leetcode.com/problems/longest-substring-without-repeating-characters/

　　满足这样条件的子串最大长度：子串中没有重复字符

题目分析

　　暴力解法，枚举子串的首位置，求最大的不重复子串的长度，并借助hashmap，复杂度是O(n^2)。看了一下disscuss区竟然有o(n)的，思路是有两个指针，一个作为子串的左边界，另一个作为右边界。借助hashmap，key是字符，value是字符的index，遇到已在hashmap的字符就要将左边界右移（注意左边界只能向右），然后put进入hashmap，并更新max值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int i = 0;//right
        int j = 0;//left
        int max = 1;
        Map<Character, Integer> map = new HashMap<>();
        for(i = 0; i < len; i++) {
            if(map.containsKey(s.charAt(i))) {
                j = Math.max(j,  map.get(s.charAt(i)) + 1); // 这里注意j的值不能变小，举个例子:"abba"
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}

　　时间复杂度 O(n)