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