LeetCode 3. 无重复字符的最长子串
题目描述
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释:最长的无重复字符的子串是 "abc",其长度为 3。
示例 2:
输入: s = "bbbbb"
输出:1
解释:最长的无重复字符的子串是 "b",其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释:最长的无重复字符的子串是 "wke",其长度为 3。
提示:
0 <= s.length <= 5 * 10^4
-
s
由英文字母组成
Java 实现代码
import java.util.HashMap;
public class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(map.get(s.charAt(right)) + 1, left);
}
map.put(s.charAt(right), right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
解题思路
- 滑动窗口:使用两个指针
left
和right
表示当前子串的边界。- 哈希表:用一个哈希表存储字符及其最新出现的位置。
- 遍历字符串:
- 当遇到重复字符时,更新
left
指针,以确保子串中没有重复字符。- 更新哈希表中的字符位置,并计算当前子串的长度,更新最大长度。
复杂度分析
- 时间复杂度:O(n),其中 n 是字符串的长度,滑动窗口遍历了字符串一次。
- 空间复杂度:O(min(n, m)),其中 n 是字符串的长度,m 是字符集的大小。哈希表的空间复杂度与字符集大小有关。