【经典算法题】无重复字符的最长子串

题目描述：Leetcode 0003 无重复字符的最长子串

分析

• 本题的考点：双指针、哈希表。

• 本题中使用到双指针的技巧，具体来说是双指针中的滑动窗口技巧；双指针中还包括对撞指针技巧。

• 我们使用[j, i]表示当前没有重复字符的窗口大小，如果当前考察的字符和窗口中的字符重复了，则让j不断后移直到没有重复字符即可。

• 还有一个问题，我们如何判断当前考察的字符和窗口[j, i]中的字符重复了？可以使用哈希表，这里使用一个长度为128的数组即可，因为ASCII码的范围为0~127，例如如果f[97] == 1成立，则说明窗口[j, i]中包含字符a。

代码

• C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        vector f(128, 0);  // 表示窗口[j, i]中字符出现的频率
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i++) {
            f[s[i]]++;
            while (f[s[i]] > 1) f[s[j++]]--;
            res = max(res, i - j + 1);
        }
        return res;
    }
};

• Java

class Solution {
    public int lengthOfLongestSubstring(String s) {

        char[] cs = s.toCharArray();

        int[] f = new int[128];  // 表示窗口[j, i]中字符出现的频率
        int res = 0;
        for (int i = 0, j = 0; i < cs.length; i++) {
            f[cs[i]]++;
            while (f[cs[i]] > 1) f[cs[j++]]--;
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

• Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        f = [0 for _ in range(256)]
        j = res = 0
        for i in range(len(s)):
            f[ord(s[i])] += 1
            while f[ord(s[i])] > 1:
                f[ord(s[j])] -= 1
                j += 1
            res = max(res, i - j + 1)
        return res

时空复杂度分析

• 时间复杂度： O ( n ) O(n) O(n)，n为字符串长度。

• 空间复杂度： O ( 1 ) O(1) O(1)。