长期更新，对使用 Java 刷 LeetCode 过程中一些有趣的题的感想和启发。 解题源代码仓库

题目

题目链接

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例 1:

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

输入: “bbbbb” 输出: 1 解释: 无重复字符的最长子串是 “b”，其长度为 1。 示例 3:

输入: “pwwkew” 输出: 3 解释: 无重复字符的最长子串是 “wke”，其长度为 3。 请注意，答案必须是一个子串，”pwke” 是一个子序列 而不是子串。

我的思路

思路如下：

  1. 首先从第零位开始先找一个最小不重复字符串赋给 output；
  2. 首位从第一位到第 (size - output.length()) 位重复寻找不重复字符串赋给 tempOutput；
  3. 若 temOutput 的长度大于 output ,则将 tempOutput 赋给 output；

我的代码



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
34
35
36
37
38
39
40
41
42
43



//解决方法
class Solution {
    public int lengthOfLongestSubstring(String s) {
        String output = "";
        String tempOutput = "";
        //寻找从第一位开始的最小不重复字符串
        for (int i = 0;i < s.length();i++) {
            if (!isReapeat(output, s.charAt(i))) {
                output = output + s.charAt(i);
            }else {
                break;
            }
        }

        // i 是首位的指针。
        for (int i = 1;i < s.length() - output.length();i++){
            tempOutput = "";
            // j 是循环找不重复数的指针
            for (int j = i;j < s.length();j++) {
                if (!isReapeat(tempOutput,s.charAt(j))) {
                    tempOutput = tempOutput + s.charAt(j);
                }else{
                    break;
                }
            }
            if (tempOutput.length() > output.length()) {
                output = tempOutput;
            }
        }
        return output.length();
    }

    public boolean isReapeat(String str, char c){
        for (int i = 0;i < str.length();i++) {
            if (c == str.charAt(i)) {
                return true;
            }
        }
        return false;
    }
}

结果

987 个测试数据通过了 986 个，但在最后一个 input 中超（tai)时(cai)了。

复杂度分析

时间复杂度:

O(n^3)

时间复杂度:

O(min(n,m))

标准解题思路1:滑动窗口

暴力法非常简单。但它太慢了。那么我们该如何优化它呢？

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 i 到 j-1 之间的子字符串 {s_{ij}} 已经被检查位没有重复字符。我们就只需要检查 s[ j ] 对应的字符是否已经存在于子字符串 {s_{ij}} 中。

要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2) 的算法，但我们可以做得更好。

通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [ i,j ) （左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [ i,j ) 向右滑动 1 个元素，则它将变为 [ i+1,j+1 ) （左闭，右开）。

回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [ i,j ) (最初 j=i ) 中。然后我们向右侧滑动索引 j ，如果它不在 HashSet 中，我们会继续滑动 j 。直到 s[ j ] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

复杂度分析

时间复杂度:

O(2n)=O(n)

在最糟糕的情况下，每个字符将被 i 和 j 访问两次。

空间复杂度:

O(min(m,n))

代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            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:优化的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果 s[ j ] 在 [ j,i ) 范围内有与 j^{'} 重复的字符，我们不需要逐渐增加 i 。我们可以直接跳过 [ i,j^{'} ] 范围内的所有元素，并将 i 变为 j^{'}+1 。

Java（使用 HashMap）



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15



public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

Java（假设字符集为 ASCII 128）

以前的我们都没有对字符串 s 所使用的字符集进行假设。

当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

  1. int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
  2. int [128] 用于ASCII码
  3. int [256] 用于扩展ASCII码


1
2
3
4
5
6
7
8
9
10
11
12
13



public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

复杂度分析

时间复杂度:

O(n)

空间复杂度（HashMap）:

O(min(m,n))

空间复杂度（Table）:

O(min(m))

本文作者 Auther：Soptq

本文链接 Link： https://soptq.me/2018/10/03/leetCode3/

版权声明 Copyright： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处。 Content on this site is licensed under the CC BY-NC-SA 4.0 license agreement unless otherwise noted. Attribution required.


发现存在错别字或者事实错误？请麻烦您点击 这里 汇报。谢谢您！