LeetCode 3. 无重复字符的最长子串 (从暴力到滑动窗口——滑动窗口经典入门题)

无重复字符的最长子串 滑动窗口做法就不说了。 主要讲一讲为什么可以用这种做法，或者说暴力方法的优化点在哪。 考虑一种最暴力的方法： 对一个字符串的每个子串（共有$(n+1)\ast n/2$个），调用一个检查其合法性的函数（判断是否有重复字符），更新子串的最大值。 时间复杂度：$O(n^3)$

class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0; for(int i=0;i<s.size();i++){ for(int j=i;j<size();j++){ if(isValid(l,r,s){ ans = max(ans,r-l+1); } } } return ans; } bool isValid(int l,int r,const string &s){ //………………………… } };

优化点：

首先，如果序列$[i,j]$不合法，那么序列$[i,j+1]、[i,j+2]\dots \dots$就都不合法了。其次，如果[i,j]合法，那么$[i+1,j]、[i+2,j]、[i+3,j]\dots \dots$也都合法(虽然不会更新最大值)，这样也不用在枚举$i+1$为起点的时候，再将指针$j$依次加到上个$j$。最后，也没有必要每次都用遍历字符串来检查，我们用一个bool vis[]或者set<char>记录一下$[l,r]$出现的值就好。 时间复杂度:$O(n)（O(n\ast log(n))）$ class Solution { public: int lengthOfLongestSubstring(string s) { bool vis[256] = {0}; int l=0,r=0,ans=0,n=s.size(); while(l<n && r<n){ while(r<n && !vis[s[r]]){ vis[s[r]] = 1; r++; } ans = max(ans,r-l); vis[s[l]]=0; l++; } return ans; } };