做推送的网站有哪些,专业网站建设-好发信息网,有没有免费的网站服务器,做门户网站的营业范围无重复字符的最长子串 给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最…无重复字符的最长子串 给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
题解: 朴素解法当然是考虑n^2算法,就是枚举两个端点,选出最优解 是否可以优化? 比如abcabcbb串中 abcabcbb abc bca 由abc直接跳到bca而不再暴力搜索 b,bc,是因为我们在abc这里就已经知道bc是符合条件的字串,只是由于a与新字符不满足条件所以我们要拿掉a,防止重复考虑剩下的满足条件的字符串,最终得到解.
所以高效一点的解法就是用两个指针分别指向满足条件的左端和右端,若是满足条件就让右指针前进,不满足条件,就让左指针前进到满足条件的位置继续搜索,这个算法就是twopointer算法,也可以叫滑动窗口算法,因为这个算法left和right两个指针走一遍序列就可以搜出最优解,所以是O(n).
这个算法可以巧妙地避免中间已经比较过的序列,减少二次比较从而优化算法效率. 我们可以保存一个当前子串中的字符的位置,如果这个字符之前遇到过,我们就让left前进到这个之前遇到过的位置的后一个元素,让后的过程把这些字符都从我们的保存位置表中删掉.这样就能减少重复比较,没必要让left1后再进行条件判断.
class Solution {
public:mapchar,intbok;int lengthOfLongestSubstring(string s) {int left 0,right -1,maxlen0;while(1){right;if(rights.length()){maxlen max(maxlen,right-left);break;}if(bok.count(s[right])0){bok[s[right]]right;}else {maxlen max(maxlen,right-left);int start left;left bok[s[right]]1;while(startleft)bok.erase(s[start]);bok[s[right]] right;}}return maxlen;}
};
