最长无重复子字符串数据结构和刷题

https://leetcode.com/problems/longest-substring-without-repeating-characters/
剑指offer上的解法是动态规划，即：
f(i)表示当前i位置字符结尾的子字符串的最长无重复结果
那么考虑两种情况：
（1）当前位置的字符距离其上一次出现的距离 d 大于当前长度，则说明该字符未出现在当前字符，直接加上当前字符；
（2）若<= 则出现过，那么以当前字符结尾的最长无重复，就是 i - pre_i

class Solution {public:int lengthOfLongestSubstring(string s) {int pos[256]; for (int i=0; i<256; i++)pos[i] = -1; int curl = 0; int maxl = 0; for (int i=0; i.size(); i++) { //cout if (pre_i<0 || (i-pre_i)>curl) { curl++; }else{if (curl>maxl)maxl = curl; curl = i - pre_i; }pos[s[i]] = i; if (curl>maxl)maxl = curl; }return maxl; } };

还有一种滑动窗口的思路：
https://www.cnblogs.com/grandyang/p/4480780.html
map建立映射，字符-》位置：

class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0 ,left = -1; unordered_mapmp; for (int i=0; i.size(); i++ ) { if (mp.count(s[i]) && mp[s[i]]>left) { left = mp[s[i]]; } mp[s[i]] = i; res = max(res,i-left); } return res; } };

【最长无重复子字符串】下面这种写法是上面解法的精简模式，这里我们可以建立一个256位大小的整型数组来代替HashMap，这样做的原因是ASCII表共能表示256个字符，但是由于键盘只能表示128个字符，所以用128也行，然后我们全部初始化为-1，这样的好处是我们就不用像之前的HashMap一样要查找当前字符是否存在映射对了，对于每一个遍历到的字符，我们直接用其在数组中的值来更新left，因为默认是-1，而left初始化也是-1，所以并不会产生错误，这样就省了if判断的步骤，其余思路都一样：

class Solution { public: int lengthOfLongestSubstring(string s) { int res = 0 ,left = -1; vectorm(256,-1); for (int i=0; i.size(); i++ ) { if (m[s[i]]>left)left = m[s[i]]; m[s[i]] = i; res = max(res,i-left); } return res; } };