淘宝做导航网站,空间设计说明怎么写,seo优质友链购买,山西住房城乡建设厅网站题目 给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解…题目 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。
思想滑动窗口 滑动窗口是一种在数组或字符串上进行迭代的算法通过维护一个子数组或子串该子数组或子串的大小在迭代过程中可以变化。该子数组或子串的起始位置通过滑动进行调整从而找到符合特定条件的解。 滑动窗口的窗口大小是动态变化的当发现重复字符时通过调整窗口的起始位置来实现。这样你能够在遍历字符串的过程中找到不包含重复字符的最长子串同时利用 max 变量来记录最大长度。 滑动窗口是解决一类子串或子数组问题的常见思想通常用于解决找到不重复元素的最长子串或子数组的问题。这种方法的优势在于它可以在线性时间内解决问题而不需要嵌套循环。 算法分析 1. 初始化变量max 用于存储最长子串的长度index 用于跟踪重复字符的索引空字符串 str 用于存储当前子串。 2. 使用 for 循环遍历输入字符串 s 中的每个字符。 3. 在循环内部通过使用 indexOf 方法检查当前字符 ch 是否已经存在于当前子串 str 中。如果存在index ! -1则表示找到了重复的字符。 4. 如果找到重复的字符通过比较当前子串 str 的长度和当前最大长度 max 来更新 max 长度。然后通过删除从子串开头到重复字符包括重复字符的字符来更新子串 str并将当前字符 ch 连接到子串中。 5. 继续循环。 6. 如果未找到重复字符简单地将当前字符 ch 连接到子串 str 中。 7. 循环结束后比较最终子串 str 的长度和当前最大长度 max以确保最后一个子串也被考虑在内。 8. 返回最大长度。 class Solution {public int lengthOfLongestSubstring(String s) {int max0;int index-1;String str;for(int i0;is.length();i){char chs.charAt(i);indexstr.indexOf(ch);if(index!-1){maxMath.max(str.length(),max);strs.substring(i-(str.length()-1-index),i1);continue;}strstrch;}maxMath.max(str.length(),max);return max;}
}
运行结果
总的时间复杂度为 O(n)
击败百分之5%的对手。。。emmm被我击败南坪 算法调优
这时官方的解法思想也是滑动窗口来看看有什么区别
时间复杂度是O(n^2) 它采用一个Set集合然后左指针指向i ,右指针指向rk rk从一个开始逐个遍历增加不同的值加入集合 一旦有相同的值就说明此i指向的值的最长长度已经到了让左指针i指向下一个值。 rk不用更新回去因为从i到rk是不重复的那从i1到rk也肯定是不重复的所以rk不用更新回去set集合也不用清空。 每次左指针移动前要更新最长的长度 SetCharacter occ new HashSetCharacter();: 创建一个哈希集合 occ用于记录当前窗口中字符的出现情况。
int rk -1, ans 0;: 定义右指针 rk 初始值为 -1用于表示当前窗口的右边界。ans 用于记录最长子串的长度。
occ.remove(s.charAt(i - 1));: 在每次移动左指针时从哈希集合中移除左指针所指向的字符表示该字符不再属于当前窗口。
while (rk 1 n !occ.contains(s.charAt(rk 1))) { ... }: 在每次移动右指针时不断地向右移动直到遇到重复字符或者到达字符串的末尾。在移动的过程中将新的字符加入哈希集合。
ans Math.max(ans, rk - i 1);: 在每一步迭代中更新最长子串的长度。
class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合记录每个字符是否出现过SetCharacter occ new HashSetCharacter();int n s.length();// 右指针初始值为 -1相当于我们在字符串的左边界的左侧还没有开始移动int rk -1, ans 0;for (int i 0; i n; i) {if (i ! 0) {// 左指针向右移动一格移除一个字符occ.remove(s.charAt(i - 1));}while (rk 1 n !occ.contains(s.charAt(rk 1))) {// 不断地移动右指针occ.add(s.charAt(rk 1));rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans Math.max(ans, rk - i 1);}return ans;}
}
时间耗时6ms确实比我块的多但是时间复杂度很大。懂得都懂
