[hot100] 无重复字符的最长子串

无重复字符的最长子串题目的意思就是给你一个字符串要你求出它里面的最长的字串但是这个字串里面不能有重复的其实这个题目还是有点绕的我们看到子串这两个字时候就要联想到滑动窗口其实滑动窗口这个算法的本质就是在动态切割一个数组或者字符串这个就有点像把一个口子里面装上了一个窗口可以滑动窗户来动态控制这个口子的大小回归到题目如果只是单纯的找子串那这个题目就没有任何意义了但是这个题目要求子串不能有重复的那怎么保证没有重复呢其实第一反应是不是应该就是用hashmap把这个值存入key或者value中然后判断后续遍历的字符串是不是在这个里面如果在的话说明重复了那就应该移动左边的“窗口”让它保持无重复字符这里的hashmap(py里的字典)就是记录的就是遍历元素的时候上次出现字符的位置上述问题的大体流程为但是这里有一个最难的就是要判断上次出现的字符是不是还在这个窗口里面也就是说可能map里面记录的值早就不在窗口区间里面了所以这个时候就需要判断map里面存在的值是否大于left 也就是窗口的最左边才能保证继续移动eg字符串为abba的时候当right遍历到第二个b上的时候left就已经移动到这里了然后下次再遍历a的时候这个时候第一个a已经不在窗口里面了所以不需要移动了用图的话就是这样表示这个题目如果纯看代码可能有点抽象所以需要结合图来看会比较好一些