力扣-3-无重复字符的最长字串
做之前看题目的印象是“动态规划”，因为好像和以前做的“最大子数和”看起来有点像
查看标签有“滑动窗口”，这个见过听过，但是不知道具体是什么，但是有印象，计网里的拥塞控制也用到了“滑动窗口”的概念
感觉题目降低难度了，只是要求返回长度不是要求返回子串
有了计网“滑动窗口”的概念，我想是需要两个指针来表示窗口的，头指针表示窗口起始，尾指针表示窗口末尾。另外拿一个变量来记录窗口长度
感觉难点在于：
- 如何高效地判重
我想起了刚刚做的题，用set，如果把字串中的字符放到set中，然后用count函数来判断
那么，试试吧
int lengthOfLongestSubstring(string s) {
set st;
int begin = 0,ret =0;
for(int end = begin;end 第一版，三个示例通过了就迫不及待地提交，结果空字符就报错了
检查一遍健壮性
随手编了一个测试用例，发现一个问题：刷新窗口后set没清空
但还是不对，这是为什么？
问题应该出在最后遍历完成后没有再记录窗口长度，也就是说如果最长无重复子串在数组最后的情况
分析一下，遍历结束后，end指针应该在数组末尾，begin指针还在窗口开头
我把end改成类变量
有一个很复杂的问题，每次出现了重复字符不是把头指针与尾指针置通，而是头指针指向被重复字符的位置去，那我改map，刷新begin到被重复元素的后一个位置，然后这样又有了新问题，容器不能简单得清空了
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0;
if(s==""){
return ret;
}
map mp;
int begin = 0,end;
for(end = begin;end 这一版，能把目前的四个用例全部跑过
通过！??不过效率奇低
理一下思路
个人思路
初始窗口指针begin、end均为0，end始终向前走，begin不定时刷新，两个指针中间为“窗口”，即“目前无重复的最大字串”
1.end指针遍历字符串，
- 若map中没有该字符（即当前窗口中字符无重复），将遇到的字符插入map作为键，字符的索引作为值
- 若map中已有该字符，这时候就需要更新窗口（1. 将begin更新为被重复的元素的后一索引 2. 将原bgin到新begin之间的元素从map中删除）
- 为了保证数组遍历完时不会丢失最新的数组长度，于是每一步遍历都更新了结果的值
接下来考虑怎么优化算法的时间和空间效率
优化
首先，end指针的一次遍历过程是没法优化的，这是必须的
我想到了优化更新begin的过程
这样，当我遇到相同的了，就从begin（到end）开始遍历，如果指向的字符不等于现在的重复的字符，就踢掉，那么就可以又回到set
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0;
if(s==""){
return ret;
}
set st;
int begin = 0,end;
for(end = begin;end 好像…时间提高了一点，空间没变化
继续优化，两个思路
- 不用STL容器能否实现？
我之所以会用容器，主要还是为了保存和判相同，但判相同不是能用位运算？但是保存地数据结构就不好解决了，或者要不，干脆不解决，不用额外的空间呢
……好像不太行，遍历只会导致效率更低 - map能否更巧妙地实现？
map的优点是能保存值和索引位置
我扫描字符串，键没有，就把键（字符）值（索引）放进去，键有了，就把返回值更新为字符长度。
不不不，思路有问题
看题解了看题解了
官方题解
C++中字符数组名和字符串变量名
这一插一段，因为写的时候遇到了s==nullptr报错的情况，那么说明C++中字符串不是指针？不像是字符数组的数组名？
另外s==NULL也报错，那么它也不是对象？
我用了s==""，但究竟是怎么回事呢？
后记
哈哈哈，我还是很开心，毕竟是自己写出来的中等题（好吧，我看了标签提示）