网站建设一年能收入多少钱,福建省建设监理公司网站,什么是网站单页,东莞高埗做网站哪个公司好#x1f64b;大家好#xff01;我是毛毛张! #x1f308;个人首页#xff1a; 神马都会亿点点的毛毛张 这是一道银行的面试题#xff0c;就是简单#xff1f;#xff01; LeetCode链接#xff1a;3. 无重复字符的最长子串 1.题目描述
给定一个字符串 s #xff0c… 大家好我是毛毛张! 个人首页 神马都会亿点点的毛毛张 这是一道银行的面试题就是简单 LeetCode链接3. 无重复字符的最长子串 1.题目描述
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示 0 s . l e n g t h 5 ∗ 1 0 4 0 s.length 5 * 10^4 0s.length5∗104s 由英文字母、数字、符号和空格组成
2.题解
盲猜暴力解法肯定超时毛毛张就不在这里介绍了这个题目只需要最长子串的长度做完可以尝试一下这道题目LeetCode:67.最小覆盖子串
2.1 双指针-哈希集合
class Solution {public int lengthOfLongestSubstring(String s) {// 使用一个Set来存储当前子串中的字符SetCharacter set new HashSet();// 初始化左右指针和最大长度int left, right;int maxLen 0;// 从左到右遍历字符串for (left 0, right 0; right s.length(); right) {// 获取当前字符Character c s.charAt(right);// 如果当前字符不在Set中更新最大长度if (!set.contains(c)) {maxLen Math.max(maxLen, right - left 1);}// 如果当前字符在Set中则移动左指针直到没有重复字符while (set.contains(c)) {set.remove(s.charAt(left));left;}// 将当前字符添加到Set中set.add(c);}// 返回最大长度return maxLen;}
}2.2 双指针-哈希数组
如果能用哈希集合那么大概率也可以使用哈希数组
class Solution {public int lengthOfLongestSubstring(String s) {// 使用一个大小为128的整数数组来记录字符出现的次数int[] arr new int[128];// 初始化左右指针和最大长度int left, right;int maxLen 0;// 从左到右遍历字符串for (left 0, right 0; right s.length(); right) {// 获取当前字符char c s.charAt(right);// 如果当前字符在数组中的计数为0更新最大长度if (arr[c] 0) {maxLen Math.max(maxLen, right - left 1);}// 如果当前字符在数组中的计数不为0则移动左指针直到没有重复字符while (arr[c] ! 0) {arr[s.charAt(left)]--;left;}// 将当前字符的计数加1arr[c];}// 返回最大长度return maxLen;}
}
