3LongestSubstringWithoutRepeatingCharacters.org

[#B] 3 Longest Substring Without Repeating Characters - LeetCode

思路：通过滑动窗口来遍历整个字符串，把遍历过的字符数记录下来，如果有重复数量就会为1。在没有重复的情况下滑动窗口的右边界，往右移动，对应字符数 +1，表示这个字符之前没有出现过，可以往里面添加新的字符。有重复的情况下，滑动窗口的左边界往右移动，同时对应的字符数 -1。

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int r = -1;
        int[] freq = new int[256];
        int length = 0;
        while (l < s.length()) {
            // r + 1 不能超过字符串长度， r + 1 位置上字符为 0 表示没有重复
            if (r + 1 < s.length() && freq[s.charAt(r + 1)] == 0) {
                // r + 1 位置上的字符数 +1，r 往右移动
                freq[s.charAt(++r)]++;
            }else {
                // l 位置上字符数 -1， l 往右移动
                freq[s.charAt(l++)]--;
            }
            length = Math.max(length, r - l + 1);
        }
     
        return length;
    }
}

CPP

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0;
        int r = -1;
        // 别忘了这里要赋初值为 0
        int freq[256] = {0};
        int res = 0;
        while (l < s.size()) {
            if (r + 1 < s.size() && freq[s[r + 1]] == 0) {
                freq[s[++r]]++;
            }else {
                freq[s[l++]]--;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};