leetcode
leetcode 2901 ~ 2950
无重复字符的最长子串

无重复字符的最长子串

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 39 ms, 内存: 16.2 MB


/*
 * 思路:使用Java Stream API来简化代码
 * 我们将字符串转化为字符流,并使用distinct()方法过滤重复字符
 * 然后使用滑动窗口的思想,找到最长无重复字符的子串长度
 */
import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        return IntStream.range(0, s.length())
                .map(i -> {
                    map.put(s.charAt(i), i);
                    return map.size();
                })
                .reduce(0, (max, cur) -> Math.max(max, cur));
    }
}

解释

方法:

题解采用的是滑动窗口技术来找出不含有重复字符的最长子串。维护两个指针(begin和end)作为窗口的边界,以及一个哈希表tt来记录每个字符最近一次出现的位置。随着end指针的遍历,如果当前字符s[end]未出现过或者其上一次出现的位置在窗口左边界begin之前,那么更新该字符的位置并计算当前窗口的长度。如果发现重复字符,即s[end]出现的位置在begin之后或等于begin,则更新begin到该字符上次出现位置的下一个位置,重新定义窗口的左边界。这样,每步都可能更新最长子串的长度。

时间复杂度:

O(n)

空间复杂度:

O(m)

代码细节讲解

🦆
滑动窗口中,当遇到重复字符时,为什么将begin指针更新到重复字符的下一个位置而不是其他位置?
当遇到重复字符时,更新begin指针到重复字符的下一个位置是为了确保窗口中不包含任何重复字符,并且这种移动是最小的有效移动。将begin移动到这个位置可以保留窗口中尽可能多的非重复字符,从而有机会在接下来的扩展中寻找更长的无重复子串。如果移动到其他位置,比如重复字符之前或更远的位置,将不必要地缩小窗口大小或错过潜在的最长无重复字符子串。
🦆
在哈希表tt中,你是如何决定何时更新字符的索引位置?
在哈希表tt中,字符的索引位置每次遇到该字符时都会更新。无论该字符是否在当前窗口内,只要字符被遍历到,其在哈希表中的索引就会被更新为当前的索引。这样做可以确保不管窗口如何移动,哈希表总是保持着每个字符最后一次出现的位置,这对于判断字符是否在当前窗口内以及决定窗口的左边界位置至关重要。
🦆
如果字符串包含除英文字母、数字、符号和空格以外的字符,你的算法需要做哪些调整?
如果字符串包含如Unicode字符等其他类型的字符,算法本身并不需要做根本性的调整,因为Python的字典(哈希表)可以处理各种类型的键。然而,为了确保算法处理大范围的字符集时的性能,可能需要考虑如何有效地管理哈希表的大小和查找效率。此外,如果是在其他编程语言中实现,需要确保字符编码正确处理,并且哈希函数能够适应更广泛的字符输入。

相关问题