LeetCode 3 - 无重复字符的最长子串

AlightYoung 11/23/2019 LeetCode

中等

原题链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ (opens new window)

# 题目描述

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

示例 1

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

示例 2

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

示例 4

输入: s = ""
输出: 0

提示

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

# Java题解

# 方法一暴力法

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

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) {
        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;
    }
}

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(), 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;
    }
}

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

// int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
// int [128] 用于ASCII码
// int [256] 用于扩展ASCII码
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;
    }
}

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

# 总结

该题最大的收获，可能就是了解到了滑动窗口的概念吧。

还有就是即使是暴力法，也可能出现考虑不周全导致复杂度增加的可能，比如这样：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=1;
        if(s.length()==0) {
            max=0;
            return max;
        }else{
            for(int i=0;i<s.length();i++){
                for(int j=i+1;j<s.length();j++){
                    if(allUnique(s,i,j)) max=Math.max(max,j-i+1);
                }
            }
            return max;
        }
    }
    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for(int i=start;i<=end;i++){
            char ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

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

8说了，算法是真的🐂🍺！

A·Y

Choose mode