题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 :
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
C++
1.滑动窗口（双指针法）+hash
一开始联想到kmp，然后发现实际还是双指针法的运用，最后看题解这也叫滑动窗口，确实和计网中的滑动窗口挺像
思路是从开始记录两个指针，第一个指针表示从它开始的最长子串长度，第二个通过移动对比前面是否出现过该字符来记录最长长度（利用hash思想），len=后-前+1；
其实题目也可以开hash数组（应该更快），这里熟悉一下set，用unordered_set来做映射
时间复杂度O（n），空间O（1）
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char> hash; int n=s.length(); if(n<2)return n; int k=0,ans=1; for(int i=0;i<n;i++){ while(k<n&&!hash.count(s[k])){ hash.insert(s[k]); ans=max(ans,k-i+1); k++; } hash.erase(s[i]); if(n-i<ans)break;//剪枝 } return ans; } };
Python
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans=0 left=0 right=0 hashset=set([]) n=len(s) while left<n: while right<n and s[right] not in hashset: hashset.add(s[right]) ans=max(ans,right-left+1) right+=1 hashset.remove(s[left]) left+=1 if n-left <ans: break return ans
java
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> hashset=new HashSet<Character>(); int ans=0,k=0; int n=s.length(); for(int i=0;i<n;i++){ while(k<n && hashset.contains(s.charAt(k))==false){ hashset.add(s.charAt(k)); ans=Math.max(ans,k-i+1); k++; } hashset.remove(s.charAt(i)); } return ans; } }
