高端网站建设企业网站建站,上海公共招聘网首页,小程序源码资源,最新网站开发工具LeetCode 3. 无重复字符的最长子串
题目描述
给定一个字符串#xff0c;请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释#xff1a;最长的无重复字符的子串是 abc#xff0c;其长度为 3。示例 2:
输入…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^4s 由英文字母组成
Java 实现代码
import java.util.HashMap;public class Solution {public int lengthOfLongestSubstring(String s) {HashMapCharacter, 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 是字符集的大小。哈希表的空间复杂度与字符集大小有关。
