MENU

LeetCode3. Longest Substring Without Repeating Characters(滑动窗口)

2019 年 01 月 27 日 • 阅读: 1014 • LeetCode阅读设置

LeetCode3. Longest Substring Without Repeating Characters(滑动窗口)

  • Medium
  • Accepted:718,947
  • Submissions:2,770,824

Description

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

链接

https://leetcode.com/problems/longest-substring-without-repeating-characters/

题意

给定一个字符串,求没有重复字符的最长子串。

题解

  • 暴力求解,两层循环找出所有子串,再加一层循环判断子串中是否含有重复字符,时间复杂度$O(n^3)$
  • 对暴力求解进行优化,在暴力求解中,我们对于子串进行了多次判断,没有必要。实际上对于一个已经判定不含重复字符的子串$S_{i,j} (S[i]...S[j-1])​$,只需判断$S[j]​$是否在该子串$S_{i,j}​$中即可,扫描子串一层循环,判断一层循环,时间复杂度$O(n^2)​$
  • 实际上判断我们没有必要循环,只需要用unordered_set存储,然后$O(1)$查询,时间复杂度$O(n)$,最坏时是$O(2n)$,会让i和j都遍历一遍
  • 具体操作,使用“滑动窗口”,$[i, j)$表示字符串$(S[i]...S[j-1])$(左闭右开),$i$和$j$可以向左向右移动。初始时,$i$,$j$都为0,然后判断当前字符$s[j]$,如果$s[j]$不在已判断的子串中,那么$j$向右滑动一位,如果$s[j]$在左边已判断的子串中,那么$i$向右滑动一位,直至$s[j]$不在$(S[i]...S[j-1])$中,答案就是整个过程中子串长度$(j-i)$的最大值
  • 其实当$s[j]$在左边已判断的子串中时,无需让$i$每次向右滑动一位,更好的做法是直接让$i$移动到出现$s[j]$位置的右边一位,但是这样的话我们就需要记录位置,得使用unordered_map来存储

代码

  • Runtime: 24 ms, faster than 33.41% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int i = 0, j = 0, ans = 0;
        unordered_set<char>uset;
        uset.clear();
        while (i < len && j < len)
        {
            if (!uset.count(s[j])) // s[j] 不在字符串中
            {
                uset.insert(s[j++]); // 向右滑动一位
                ans = max(ans, j - i); // 答案就是子串长度最大值
            }
            else // s[j] 在字符串中
                uset.erase(s[i++]); // 删到没有s[j]为止
        }
        return ans;
    }
};
  • Runtime: 32 ms, faster than 24.19% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int i = -1, j = 0, ans = 0;
        unordered_map<char, int>umap;
        umap.clear();
        while (i < len && j < len)
        {
            if (umap.count(s[j]) && umap[s[j]] > i) // 出现s[j]的位置在i的右边
                i = umap[s[j]]; // i直接移向该位置
            umap[s[j]] = j;
            ans = max(ans, j - i);
            j++;
        }
        return ans;
    }
};

话说第二种做法比第一种做法还要慢些是什么鬼,不知道神仙们是怎么写的,但是改成这种写法就快一些了,实际上$i<len$判断是没有必要的,其实需要在循环体内部改变循环变量的值的话就用while比较好,而每次循环 循环变量只增加1的话还是用for比较好。

  • Runtime: 16 ms, faster than 72.81% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int left = -1, ans = 0;
        unordered_map<char, int>umap;
        umap.clear();
        for (int i = 0; i < len; ++i)
        {
            if (umap.count(s[i]) && umap[s[i]] > left)
                left = umap[s[i]];
            umap[s[i]] = i;
            ans =max(ans, i - left);
        }
        return ans;
    }
};

果然还有一种更牛逼的做法,没必要使用unordered_map来存,用个长度为128的vector就够了,从字符串的ascii码角度来考虑,具体见代码。

  • Runtime: 12 ms, faster than 99.08% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int ans = 0, left = -1;
        vector <int> v(128, -1);
        for (int i = 0; i < len; ++i)
        {
            left = max(left, v[s[i]]);
            v[s[i]] = i;
            ans =max(ans, i - left);
        }
        return ans;
    }
};
  • “真滑动窗口”(2019年2月5日)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int cnt[256] = {0};
        int l = 0, r = - 1; // 滑动窗口s[l, r]
        int ans = 0;
        while (l < len)
        {
            if (r + 1 < len && cnt[s[r + 1]] == 0) // 非重复字符
            {
                cnt[s[++r]]++;
                ans = max(ans, r - l + 1);
            }
            else
                cnt[s[l++]]--;
        }
        return ans;
    }
};

The end.
2019年1月27日 星期日
最后编辑于: 2019 年 02 月 05 日