LeetCode 第 3 题：无重复字符的最长子串 （滑动窗口）

方法：滑动窗口

滑动窗口模板问题：右指针先走，满足了一定条件以后，左指针向前走，直到不满足条件。

特点：左右指针的方向是一致的，并且是不回头的。

C++ 代码：

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        if (size < 2) {
            return size;
        }

        int left = 0;
        int right = 0;
        int res = 0;
        int count = 0;
        int freq[128] = {0};
        while (right < size) {
            if (freq[s[right]] == 1) {
                count++;
            }
            freq[s[right]]++;
            right++;
            while (count > 0) {
                if (freq[s[left]] == 2) {
                    count--;
                }
                freq[s[left]]--;
                left++;
            }
            res = max(res, right - left);
        }
        return res;
    }
};

Java 代码：

/**
 * @author liweiwei1419
 * @date 2019/9/23 11:34 下午
 */
public class Solution5 {

    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) {
            return len;
        }
        int res = 0;
        // 表示边界条件，重复次数
        int count = 0;

        int[] hash = new int[128];
        int left = 0;
        int right = 0;
        while (right < len) {
            if (hash[s.charAt(right)] == 1) {
                // 当前看到的 right 多于 1 个，说明此时的滑动窗口有重复元素
                count++;
            }
            hash[s.charAt(right)]++;
            right++;
            while (count > 0) {
                // 如果正好遇到重复的那个字符，就可以退出循环了
                if (hash[s.charAt(left)] == 2) {
                    count--;
                }
                hash[s.charAt(left)]--;
                left++;
            }
            // 此时 (left, right] 这个区间内没有重复元素
            // (3, 5]，[4,5]
            res = Math.max(res, right - left);
        }
        return res;
    }
}

Python 代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return size
        left = 0
        right = 0
        hash = [0] * 128
        res = 0
        count = 0
        while right < size:
            if hash[ord(s[right])] == 1:
                count += 1
            hash[ord(s[right])] += 1
            right += 1

            while count == 1:
                if hash[ord(s[left])] == 2:
                    count -= 1
                hash[ord(s[left])] -= 1
                left += 1
            res = max(res, right - left)
        return res