【重点】【滑动窗口】3. 无重复字符的最长子串-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134764019

该博客围绕无重复字符的最长子串问题，参考《算法小抄》解法，重点讲解滑动窗口方法。提供了Python和Java两种语言的实现，Python有Counter版和常见版，Java有两种不同方法，还提及参考了灵茶山艾府的内容。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目
参考《算法小抄》重的解法，重点理解！！！

Python

Counter版

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cntS = Counter()
        res, left = 0, 0
        for right, x in enumerate(s):
            cntS[x] += 1
            while cntS[x] > 1:
                cntS[s[left]] -= 1
                left += 1
            res = max(res, right - left + 1)
        
        return res

常见版

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i, j = 0, 0
        max_len = 0
        used_set = set()
        s_array = list(s)
        while i < len(s_array) and j < len(s_array):
            if s_array[j] not in used_set:
                used_set.add(s_array[j])
                max_len = max(max_len, j - i + 1)
                j += 1
            else:
                used_set.remove(s_array[i])
                i += 1

        return max_len

Java

法1

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() < 2) {
            return s.length();
        }
        char[] array = s.toCharArray();
        int left = 0, right = 0, res = 0;
        int[] count = new int[256];
        while (right < array.length) {
            char cur = array[right];
            ++right;
            ++count[cur];
            while (count[cur] > 1) {
                char d = array[left];
                ++left;
                --count[d];
            }

            res = Math.max(res, right - left);
        }

        return res;
    }
}

法2

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, maxLen = 0;
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            char curChar = s.charAt(right);
            ++right;
            if (!set.contains(curChar)) {
                maxLen = Math.max(maxLen, right - left);
            } else {
                while (left < right - 1 && set.contains(curChar)) {
                    char tmp = s.charAt(left);
                    set.remove(tmp);
                    ++left;
                }
            }
            set.add(curChar);
        }

        return maxLen;
    }
}