Leetcode 3 Longest Substring Without Repeating Characters 题解分析

发表于 分类于 ， ， ， ， 阅读次数： 阅读次数： Disqus：

又做了个题，看记录是以前用 C++写过的，现在捋一捋思路，用 Java 再写了一下，思路还是比较清晰的，但是边界细节处理得比较差

简要介绍

Given a string s, find the length of the longest substring without repeating characters.

样例

Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

1
2
Input: s = ""
Output: 0

就是一个最长不重复的字符串长度，因为也是中等难度的题，不太需要特别复杂的思考，最基本的就是O(N*N)两重循环，不过显然不太好，万一超时间，还有一种就是线性复杂度的了，这个就是需要搞定一个思路，比如字符串时 abcdefgaqwrty，比如遍历到第二个a的时候其实不用再从头去遍历了，只要把前面那个a给排除掉，继续往下算就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    Map<String, Integer> counter = new HashMap<>();
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        // 当前的长度
        int subStringLength = 0;
        // 最长的长度
        int maxSubStringLength = 0;
        // 考虑到重复的位置已经被跳过的情况，即已经在当前长度的字符串范围之前的重复字符不需要回溯
        int lastDuplicatePos = -1;
        for (int i = 0; i < length; i++) {
            // 使用 map 存储字符和上一次出现的位置，如果存在并且大于上一次重复位置
            if (counter.get(String.valueOf(s.charAt(i))) != null && counter.get(String.valueOf(s.charAt(i))) > lastDuplicatePos) {
                // 记录重复位置
                lastDuplicatePos = counter.get(String.valueOf(s.charAt(i)));
                // 重置不重复子串的长度，减去重复起点
                subStringLength = i - counter.get(String.valueOf(s.charAt(i))) - 1;
                // 替换当前位置
                counter.replace(String.valueOf(s.charAt(i)), i);
            } else {
                // 如果不存在就直接 put
                counter.put(String.valueOf(s.charAt(i)), i);
            }
            // 长度累加
            subStringLength++;
            if (subStringLength > maxSubStringLength) {
                // 简单替换
                maxSubStringLength = subStringLength;
            }
        }
        return maxSubStringLength;
    }
}

注释应该写的比较清楚了。