【LeetCode】无重复字符的最长子串【滑动窗口法】

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

分析：

这三种方法都是属于广义上的滑动窗口法，只是采用的数据结构以及一些操作有所不同

方法一：采用set判断子串中是否存在该字符

暴力的复杂度在于判断一个字串里面是否存在该字符，需要遍历子串，导致暴力的时间复杂度为O(N^2),判断一个字符是否存在于子串中可以采用set集合判断，这样子串中判断字符是否存在的时间复杂度为O(1)

时间复杂度：O(2*N)=O(N)，在最糟糕的情况下，每个字符将被 i 和 j访问两次。

空间复杂度: set的大小取决于字符串长度n和字符集的大小m，所以空间复杂度O(min(n,m)）

class Solution { public: int lengthOfLongestSubstring(string str) {if(str=="")return 0;set<char> ss;int i=0,j=0,n=str.length();int ans=-1;while(i<n&&j<n){if(ss.find(str[j])==ss.end()){ss.insert(str[j++]);ans=max(ans,j-i);}else{ss.erase(str[i++]);}}return ans; } };

执行时间：60 ms

方法二：采用map或者数组存储每个字符最后出现的索引位置，以便i跳跃式前进

在S[i]到S[j]内如果有字符s[k]重复于S[j+1]的话，如果采用set，i是逐渐增加的（每次前移1位），但是如果采用map存储每个字符最后出现的索引位置，这样i可以直接跳到k+1，属于跳跃式前进

字符集大小：m

时间复杂度：O(2*N)=O(N)

空间复杂度：O(m)

class Solution { public: int lengthOfLongestSubstring(string str) {if(str=="")return 0;map<char,int> mm;int i=0,j=0,n=str.length();int ans=-1;for(i=0,j=0;j<n;j++){if(mm.find(str[j])!=mm.end()){i=max(i,mm[str[j]]);}ans=max(ans,j-i+1);mm[str[j]]=j+1;}return ans; } };

执行时间：32 ms

 

方法三：采用数组存储字符索引，start代表没有重复子串的开头

如果原来出现过的字符的位置大于start，那么更新start

i-start=没有重复子串的长度

该方法省去了在子串中利用map或者set查找是否存在某字符的操作，直接判断一下当前字符出现过的最后位置是否大于start

时间复杂度:O(N)

空间复杂度：O(m),m为字符集的大小

class Solution { public:int lengthOfLongestSubstring(string str){vector<int> v(300,-1);int ans=0;int n=str.length();int start=-1;for(int i=0; i<n; i++){if(v[str[i]]>start){start=v[str[i]];}v[str[i]]=i;ans=max(ans,i-start);}return ans;} };

执行时间：8 ms

 

滑动窗口展示的动态图片请参考：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/

转载于:https://www.cnblogs.com/yinbiao/p/11271893.html

总结

以上是生活随笔为你收集整理的【LeetCode】无重复字符的最长子串【滑动窗口法】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。