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日星期日