【 LeetCode 热题 HOT 100】3. 无重复字符的最长子串 (C++ 哈希 思维)

简介: 【 LeetCode 热题 HOT 100】3. 无重复字符的最长子串 (C++ 哈希 思维)

题目链接

题意:

给出一个字符串(长度为5e4),求没有重复字符的最长连续串。

思路:

由于长度为5e4,考虑O ( n )的遍历。

用map存储在当前位置之前该字符的最后一次出现的位置是第几个。

las表示如果以当前字符串为结尾,能够保证不重复的位置。

i-las+1就是以当前字符串结尾的答案。

取最大值就好了。

代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans=0,las=0;
        //s=" "+s;
        map<char,int>mp;
        for(int i=0;s[i];i++){
            las=max(las,mp[s[i]]);
            mp[s[i]]=i+1;
            ans=max(ans,i-las+1);
           // cout<<i<<"****"<<las<<"*****"<<ans<<endl;
        }
        return ans;
    }
};
目录
相关文章
|
7天前
|
存储 算法 编译器
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
【C++ 字符数组的模板特化】面向字符串的C++模板特化:理解与实践
56 1
|
7天前
|
算法 Java C语言
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
|
2天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
7 0
|
2天前
|
数据处理 C++
C++程序字符串流
C++程序字符串流
12 2
|
2天前
|
存储 C++ 索引
C++程序字符数组:深入理解与实践
C++程序字符数组:深入理解与实践
10 2
|
7天前
|
存储 算法 数据安全/隐私保护
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]
8 0
|
7天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
11 1
|
7天前
|
存储 算法 C++
【C++高阶(六)】哈希的应用--位图&布隆过滤器
【C++高阶(六)】哈希的应用--位图&布隆过滤器
|
7天前
|
存储 Serverless C++
【C++高阶(五)】哈希思想--哈希表&哈希桶
【C++高阶(五)】哈希思想--哈希表&哈希桶
|
7天前
|
存储 编译器 Linux
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”