网页标准化对网站开发维护的好处,英文网站站长工具,品牌设计公司网站源码,做搜索网站能发财吗leetcode 3. 无重复字符的最长子串 leetcode 3. 无重复字符的最长子串 | 中等难度1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现4. 知识与收获 leetcode 3. 无重复字符的最长子串 | 中等难度
1. 题目详情
给定一个字符串 s… leetcode 3. 无重复字符的最长子串 leetcode 3. 无重复字符的最长子串 | 中等难度1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现4. 知识与收获 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.length 5 * 104 s 由英文字母、数字、符号和空格组成 1. 原题链接
leetcode 3. 无重复字符的最长子串
2. 基础框架
● Cpp代码框架
class Solution {
public:int lengthOfLongestSubstring(string s) {}
};2. 解题思路
1. 题目分析 ( 1 ) (1) (1) 本题要求字符串s的最长连续不重复子串。子串其实与子数组是相似的概念。 ( 2 ) (2) (2)
2. 算法原理 ( 1 ) (1) (1) 首先想到暴力枚举枚举出所有子串记录连续不重复子串的长度在其中找出最大的。 首先固定一个起始位置i枚举以i为开始位置的子串 如果满足新元素加入后满足题意长度len就自增1 如果不满足就说明以i为开始位置的子串在新元素及其之后的所有元素都不满足题意即出现重复元素了。所以可以直接开始枚举以i1为开始位置的子串了。 这里判断新元素是否在子串中出现不能通过在子串中搜索实现这样时间复杂度很高。优化方法是遍历子串时使用哈希数组hash记录对应字符元素出现的次数这样在判断新元素是否重复时只要查询一下hash中字符元素出现的次数即可是O(1)操作。 ( 2 ) (2) (2) 对暴力枚举的再优化滑动窗口 我们先来看一个暴力枚举时的例子 ( 3 ) (3) (3) 通过对减少暴力枚举中重复的遍历优化时间复杂度。
3. 时间复杂度
暴力枚举 O ( n 2 ) O(n^2) O(n2)
滑动窗口 O ( n ) O(n) O(n) 滑动窗口算法中left和right都只向一个方向移动不会回退直到结束最坏情况是left都和right移动到末尾时间复杂度也是 O ( n ) O(n) O(n)级别 3. 代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret 0;int hash[128];//哈希数组记录滑动窗口内元素出现的个数int l 0, r 0;while(r s.size()){hash[s[r]];//进窗口while(hash[s[r]] 1)//判断hash[s[l]]--;//滚出 窗口ret max(ret, r - l 1);//更新结果r;//让}return ret;}
};4. 知识与收获 ( 1 ) (1) (1) 滑动窗口是对暴力枚举思路的优化在理解暴力枚举的思路下发现暴力枚举中进行着大量重复的遍历操作通过设法同向双指针right不回退避免进行重复的操作降低一个维度的时间复杂度。 T h e The The E n d End End
