LeetCode刷题第3题:无重复字符的最长子串

原文链接：https://leetcode.cn/problems/longest-substring-without.../description/

题意

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

示例

示例1:

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

示例2:

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

示例3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题

• 暴力解法

解题思路

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            boolean[] book = new boolean[128]; // ASCII 字符集
            for (int j = i; j >= 0; j--) {
                if (book[s.charAt(j)]) {
                    break;
                }
                book[s.charAt(j)] = true;
                res = Math.max(res, i - j + 1);
            }
        }
        return res;
    }
}

• 查找（推荐）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[128];
        int max = 0;
        int left = 0;
        int right = 0;
        while(right<s.length()){
            left = Math.max(left, map[s.charAt(right)]);
            max = Math.max(max, right-left+1);
            map[s.charAt(right)] =++right;
        }
        return max;
    }
}

• 哈希

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;// ans用于存储最长子串的长度
        // 创建一个哈希表来记录字符最近一次出现的位置
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            // 检查当前字符是否出现过
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}