桂阳县网站建设公司哪家好,idc网站模板下载,广州短视频制作公司,p2p万能搜索引擎目录 一、题目描述
二、解题思路
1、什么是滑动窗口算法#xff1f;
2、滑动窗口一般解题模板
三、参考答案 一、题目描述 无重复字符的最长子串 给定一个字符串s #xff0c;请你找出其中不含有重复字符的最长子串的长度。 示例 1: 输入: s abcabcbb…目录 一、题目描述
二、解题思路
1、什么是滑动窗口算法
2、滑动窗口一般解题模板
三、参考答案 一、题目描述 无重复字符的最长子串 给定一个字符串s 请你找出其中不含有重复字符的最长子串的长度。 示例 1: 输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。 示例 2: 输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。 示例 3: 输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是子串的长度pwke 是一个子序列不是子串。 提示 0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成 注子串和子序列的区别子串是从一个原始字符串中直接提取的、在原字符串中连续的一段字符。例如在字符串abc中ab和bc都是其子串。相对地子序列则由原序列中不必须连续的字符组成只需保持这些字符在原序列中的相对顺序。如在字符串abc中ac构成了一个子序列。
二、解题思路 本题使用滑动窗口方法来解决。
1、什么是滑动窗口算法 滑动窗口算法是一种通过在特定数据结构上移动“窗口”来执行操作的算法。它主要用于优化时间复杂度特别是在处理数组和字符串相关问题时表现出色。滑动窗口算法的核心在于使用两个指针左指针和右指针来标识当前处理的数据范围并通过移动这两个指针来调整窗口大小同时根据具体问题的要求更新中间结果。滑动窗口算法的基本思想是通过维护一个窗口并通过移动该窗口的两个边界left 和 right 指针来处理问题。当右边界扩展到符合某种条件或者到达数据结构的末尾时再通过移动左边界来缩小窗口并在此过程中更新所需的结果。这种左右指针的移动方式使得算法能够在单次遍历中解决原本需要嵌套循环的问题从而将时间复杂度从 O(N^2) 降低到 O(N)。 2、滑动窗口一般解题模板
//外层循环扩展右边界内层循环扩展左边界
for (int l 0, r 0 ; r n ; r) {//当前考虑的元素while (l r check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意统计相关信息
}
三、参考答案 根据上述解题思路得到的参考代码如下
class Solution {public int lengthOfLongestSubstring(String s) {//滑动窗口char[] ss s.toCharArray();SetCharacter set new HashSet();//去重int res 0;//结果for(int left 0, right 0; right s.length(); right) {//每一轮右端点都扩一个。char ch ss[right];//right指向的元素也是当前要考虑的元素while(set.contains(ch)) {//set中有ch则缩短左边界同时从set集合出元素set.remove(ss[left]);left;}set.add(ss[right]);//别忘。将当前元素加入。res Math.max(res, right - left 1);//计算当前不重复子串的长度。}return res;}
} 时间复杂度分析由于每个字符最多会被访问两次起始指针和结束指针各一次所以时间复杂度为O(n)其中n为字符串的长度。 空间复杂度分析O(∣Σ∣)其中 Σ 表示字符集即字符串中可以出现的字符∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集因此可以默认为所有 ASCII 码在 [0,128) 内的字符即 ∣Σ∣128。我们需要用到哈希集合来存储出现过的字符而字符最多有 ∣Σ∣ 个因此空间复杂度为 O(∣Σ∣)。
