【Leetcode】3. Longest Substring Without Repeating Characters

题目地址https://leetcode.com/problems/longest-substring-without-repeating-characters/给定一个长n nn的字符串求其中的一个最长子串不含重复字母返回其长度。双指针 维护每个字符出现的最后位置。用一个map保存快指针遍历到j jj的时候s [ 0 , . . . , j ] s[0,...,j]s[0,...,j]所有字母最后出现的位置快指针从0 00向后遍历如果遇到了map里未保存的字符说明遇到了新字符子串可以扩展更新答案并且将该字母和它的位置存入map否则说明遇到了重复字符如果该字符出现在慢指针之后那么就将慢指针向后移动到该重复字母之前出现的位置1也就是map里存储的该字符出现的位置1否则不更新慢指针因为慢指针不能回退否则就把重复字符加进s [ i , . . . , j ] s[i,...,j]s[i,...,j]了。这样就仍然保证了[ i , j ] [i,j][i,j]里没有重复元素。代码如下classSolution{public:intlengthOfLongestSubstring(strings){unordered_mapchar,intmp;intres0;for(inti0,j0;is.size();i){if(autoitmp.find(s[i]);it!mp.end())jmax(it-second1,j);resmax(res,i-j1);mp[s[i]]i;}returnres;}};时间复杂度O ( n ) O(n)O(n)空间O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)即字母表大小。优化。signed char范围有限直接开成数组就行。并且输入可以改为string_view。代码如下classSolution{public:intlengthOfLongestSubstring(string_view s){intmp[128];memset(mp,-1,sizeofmp);intres0;for(inti0,j0;is.size();i){if(~mp[s[i]])jmax(mp[s[i]]1,j);resmax(res,i-j1);mp[s[i]]i;}returnres;}};时空复杂度不变。