• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

字符串最长子串难?滑动窗口拯救你

开发技术 开发技术 2周前 (02-19) 13次浏览

题目:leetc++ode 3. 无重复字符的最长子串

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

示例 1:

输入: s = “abcabcbb”

输出: 3 

解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

 

子串:串中任意个连续的字符组成的子序列称为该串的子串。

解题思路

要求字符串的不含有重复字符的最长子串的长度,只需要先找到最长子串然后再求其长度即可,找最长子串我们可以通过滑动窗口的方法去查找

滑动窗口

滑动窗口就是通过不断调整子序列的 start 和 end 位置,从而获取满足要求的结果。

具体操作如下:

  • 假设已经找到一个不含重复字符子串 s[left…right],s[left…right] 表示从字符串 s 的下标 left 到 right 的子串。

                 字符串最长子串难?滑动窗口拯救你

  • 子串数组的右边界 right 向右移,拓展子串长度,以寻找最长子串

    字符串最长子串难?滑动窗口拯救你

  • 将字符 s[right + 1] 跟子串 s[left…right] 中的每个字符进行比较,如果都不同,则将字符 s[right + 1] 也纳入到子串中。

    字符串最长子串难?滑动窗口拯救你

    如果字符 s[right + 1] 跟子串 s[left…right] 中的某个字符相同,则将子串数组的左边界 left 右移,刨除 s[left…right] 中的那个重复的字符

    字符串最长子串难?滑动窗口拯救你

                                                         刨除前

    字符串最长子串难?滑动窗口拯救你

                                                                刨除后

  • left 到 right 这个区间形成一个滑动窗口,为了寻找满足条件的子串,窗口不停地在向前滑动,记录子串的长度是否是更长的子串。

     

细节

如何判断右边界 right 向右拓展时,其对应的字符和当前找到的子串中无重复字符呢?一个简单的方法是:设置一个数组记录 ASCII 码出现的频率,这样当 right 向右拓展时,就可以查找其对应的字符对应的 ASCII 码在该数组中相应的频率值的多少判断是否出现了重复字符

 

Show me the Code

 1 // c 语言
 2 int lengthOfLongestSubstring(char * s){
 3     int res = 0;
 4     int len = strlen(s);
 5     /* 记录 ASCII 字符在子串中出现的次数 */
 6     int freq[256] = {0};
 7     /* 定义滑动窗口为 s[l...r] */
 8     int l = 0, r = -1;
 9     while (l < len) {
10         /* freq 中不存在该字符,右边界右移,并将该字符出现的次数记录在 freq 中 */
11         if (r < len - 1 && freq[s[r + 1]] == 0) {
12             freq[s[++r]]++;
13         /* 右边界无法拓展,左边界右移,刨除重复元素,并将此时左边界对应的字符出现的次数在 freq 的记录中减一 */
14         } else {
15             freq[s[l++]]--;
16         }
17         /* 当前子串的长度和已找到的最长子串的长度取最大值 */
18         res = fmax(res, r - l + 1);
19     }
20     return res;
21 }
字符串最长子串难?滑动窗口拯救你字符串最长子串难?滑动窗口拯救你

 1 // c++ 语言
 2 int lengthOfLongestSubstring(string s) {
 3     int res = 0;
 4     int len = s.size();
 5     int freq[256] = {0};
 6     int l = 0, r = -1;
 7     while (l < len) {
 8         if (r + 1 < len && freq[s[r + 1]] == 0) {
 9             freq[s[++r]]++;
10         } else {
11             freq[s[l++]]--;
12         }
13         res = max(res, r - l + 1);
14     }
15     return res;
16 }

View Code

更多精彩

请关注

字符串最长子串难?滑动窗口拯救你

 回复「算法」,即可获取经典高清无码算法与数据结构相关电子书籍~


程序员灯塔
转载请注明原文链接:字符串最长子串难?滑动窗口拯救你
喜欢 (0)