LeetCode50天刷题计划（Day 2—— 无重复字符的最长子串 10.00-12.00）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

机试太菜了每次都被秒杀
所以趁暑假好好练习一下吧~

一、题目描述

题目

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

示例

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

二、思路

滑动窗口的方法

滑动窗口其实就是一个队列（只能末尾进队首部出队）： 每次进队一个元素，如果发现该元素是队列中已有元素，则反复出队一个元素直至满足条件。一直维持这样的队列，找出队列出现最长的长度时候，即可求出解。
时间复杂度：O(n)

类似题目有

串联所有单词的子串
最小覆盖子串
长度最小的子数组
滑动窗口最大值
字符串的排列

三、代码

1.python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #滑动窗口数据记录
        n=len(s)
        l=[]
        #记录最大窗口值和当前窗口值
        maxWin=0
        curWin=0
        #遍历每一种情况，向窗口中依次增加元素,如果发现是窗口中已有元素，则删除左边元素直至满足条件
        for i in range(n):
            if(s[i] not in l):
                l.append(s[i])
                curWin += 1
            else:
                while (s[i] in l):
                    del l[0]
                    curWin -= 1
                l.append(s[i]) 
                curWin += 1
            #比较是否这种情况下窗口值达到最大
            if(curWin > maxWin):
                maxWin=curWin
        return maxWin

2.C++

字符串函数：
①s.size() 返回字符串长度
②s.find()返回指定范围内的第一个目标值的下标, s.end()返回最后一个元素
③s.find(i) != s.end():用find这个函数去找s字符串中是否有i这个元素，若没有该元素，则返回s.end()。
所以若s.find(i) != s.end()则表明找到了指定的i元素 等于python的 in 和 not in 关键字
④s.insert()插入字符函数
⑤s.erase(m,n); 删除从m开始的n个字符（字符串下标从0开始往下数）。
s.erase(s)内存擦除
⑥申请一个无序集合unordered_set<char> win;

unordered_set基本用法
无序集(unorder sets)是一种不按特定顺序存储唯一元素的容器，根据元素的散列值组织到桶中，因此可以根据值直接快速访问单个元素(平均时间复杂度为常数)。在unordered_set中，元素的值同时也是唯一标识它的键。键是不可变的，因此，unordered_set中的元素在容器中不能被修改，但是它们可以被插入和删除。

常用方法
unorder_set first容器定义
first.empty()判断容器是否是空，是空返回true，反之为false
first.size()返回容器大小
first.maxsize()返回容器最大尺寸
first.begin()返回迭代器开始
first.end()返回迭代器结束
first.find(value)返回value在迭代器的位置
first.count(key)返回key在容器的个数
first.insert(value)将value插入到容器中
first.erase(key)通过key删除
first.clear()清空容器

class Solution {
    
public:
    int lengthOfLongestSubstring(string s) {
    
        //定义最大长度和当前长度
        int maxLen=0;
        int curLen=0;
        //记录当前窗口左边界
        int left=0;
        //获取字符串长度
        int n=s.size();
        //建立一个窗口,申请一个无序集合
        unordered_set<char> win;
        for(int i=0;i<n;i++){
    
            //如果窗口中没找到该字符
            if(win.find(s[i])==win.end()){
    
                win.insert(s[i]);
                curLen++;
            }else{
    
                while(win.find(s[i]) != win.end()){
    
                    //不断删除窗口第一个元素直至没有重复
                    win.erase(s[left]);
                    left++;
                    curLen--;
                }
                win.insert(s[i]);
                curLen++;
            }
            //记录最大值
            if(curLen>maxLen) maxLen=curLen;
        }
        return maxLen;

    }
};