首页 > 其他 > 详细

剑指offer48. 最长不含重复字符的子字符串

时间:2020-04-09 18:17:45      阅读:57      评论:0      收藏:0      [点我收藏+]

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

分析:滑动窗口法,用一个map记录每个字符出现的位置索引,当该字符之前出现过且在当前窗口内,则窗口左端点要右移到该位置。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int n = s.size();
        int start = -1;
        int maxlen = 0;
        
        for (int i = 0; i < n; ++i) {
// 如果mp里已经存在s[i],s[i]可能在当前窗口内,也可能不在,取决于和start的相对位置 // 因此用二者的较大值更新start的位置 if (mp.count(s[i])) { start = max(start, mp[s[i]]); } // 更新s[i]位置索引 mp[s[i]] = i; maxlen = max(maxlen, i - start); } return maxlen; } };

 

剑指offer48. 最长不含重复字符的子字符串

原文:https://www.cnblogs.com/betaa/p/12668544.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!