题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke"?是一个子序列，不是子串。

知识点

• 字符串+子串
• 集合

• 滑动窗口

滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。

可以把滑动窗口看成一个队列，向右滑动的时候，就是左边元素出队

解法

思路一 暴力破解

逐个检查所有的子字符串，看它是否不含有重复的字符。
需要枚举给定字符串的所有子字符串

 for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)

检查一个字符串是否有重复字符，我们可以使用集合。我们遍历字符串中的所有字符，并将它们逐个放入 set 中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。

//Java,leetcode官方题解
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

思路二 滑动窗口

//未分析C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;//??
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    }
        return maxStr;
        
    }
};

todo list

1. 知识点需要拓展
2. 代码需要看懂
3. 代码在VS上要跑通

LeetCode_03 无重复最长子串

原文：https://www.cnblogs.com/zhuomoyixia/p/12324321.html