哈希表

无重复字符的最长子串 LeetCode算法题:3.

作者:程序员实习生 / 关注公众号:return1024  发布:2019-11-01

题目:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
题目重点:
1、不含有重复字符的最长子串的长度
思路:
用哈希表存储记录一个字符最后出现的位置
然后进行比较,一是比无重复的最早下标,二是比长度
C++题解:
28ms
class Solution {public: int lengthOfLongestSubstring(string s) { unordered_map<char,int> d; //记录字符最新出现的位置 int res = 0; int pre = -1; //最近的重复字符的位置 for(int i=0; i<s.size(); ++i){if(d.find(s[i])!=d.end()) //有出现过 pre=max(pre,d[s[i]]);res=max(res,i-pre);d[s[i]]=i; //更新位置 } return res; }};
注:思路是最重要的,本文提供的代码并非最优。


本文作者 :程序员实习生

关注Ta的微信公众号获取更多图文精彩内容...