分析

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

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

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

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

代码

• C++

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

        vector<int> 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;
    }
}

时空复杂度分析

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

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