LeetCode#3

Posted on   |   In

题目

原始地址：https://leetcode.com/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        
    }
}

描述

给定一个 字符串，找出它没有重复字母的最长子串。注意子串是原来字符串中连续的一部分。

分析

最直观的想法是暴力枚举，通过两个变量start和end做遍历，依次判断这个子串是否不 包含重复字符，最终取符合要求的子串中最长的。时间复杂度为O(n^3)，不能接受 。

如何优化这个算法呢？分析可以发现，上面这个解法中有很多次重复计算。当我们已经计算完s[i,j]这个子串，需要计算s[i,j+1]时，其实只需要判断s[j]是否包含在s[i,j]中即可，而不需要再从i算起。这样就有了解法1：i和j从头开始遍历，如果当前子串不包含下一个字符，那么我们把这个字符加到当前的子串中，并将当前的子串长度和最大值做比较；如果当前子串已经包含下一个字符，那么就把子串的起始位置向后移动即可。这种解法的时间复杂度是O(n)。

还有优化的空间吗？解法1中下一个字符已经包含在当前子串的情况下时，有可能在下次判断时当前子串依然包含下一个字符，导致else部分跑了很多遍。我们可以用一个Map来记录子串中每个字符的位置，遇到这种情况时直接将子串的起始位置跳到不包含重复字符的位置即可。具体实现见解法2，注意这时map包含不只是当前字串中的字符，有可能某个字符对应的index小于当前字串的起始位置。

解答1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, ans = 0, n = s.length();
        Set < Character > set = new HashSet < > ();
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

解答2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0, n = s.length();
        Map < Character, Integer > map = new HashMap < > ();
        for (int i = 0, j = 0; j < n; j++) {
            char c = s.charAt(j);
            if (map.containsKey(c)) {
                i = Math.max(map.get(c) + 1, i);
            }
            map.put(c, j);
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}