【LeetCode 每日一题 Day 3】3. 无重复字符的最长子串

一只编程熊

关注

发布于: 19 小时前

大家好，我是一只编程熊，今天是 LeetCode 每日一题的第三天，学习的是 LeetCode 第 3 题《无重复字符的最长子串》。

题意

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

示例

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

复制代码

题解

观察样例，我们可以发现，依次递增地枚举子串的起始位置，那么合法的结束为止一定是递增的，因为对于起始位置 i-1 ，假设其不含有重复字符的最远右位置 j；那么对于起始位置为 i 的子串，因为 [i-1，j] 不含有重复字符，其不含有重复字符的最远右位置一定大于等于 i，因此我们考虑使用滑动窗口来解决本题。

滑动窗口本质上是利用了实现了双指针，利用了指针移动的单调性，不断移动找到合法的区间，其中包含了最长的区间。

本题中，我们可以固定右指针，找到最远的不含有重复字符的左指针，根据上面我们观察得到的性质可以，不含有重复字符的左指针是非递减的。

代码具体实现上我们可以用 queue 模拟双指针，辅助数组 cnt 统计窗口内每个字符出现的次数，来判断窗口是否有重复的字符。

时间复杂度: $O (n)$

空间复杂度: $O (n)$

知识点总结: 滑动窗口

C++代码

class Solution {public:    queue<char> q;    int lengthOfLongestSubstring(string s) {        vector<char> cnt(128, 0);        int ans = 0;        for (int i = 0; i < int(s.size()); i++) {            q.push(s[i]), cnt[s[i]]++;            while (cnt[s[i]] > 1) {                char frontC = q.front();                q.pop();                cnt[frontC]--;            }            ans = max(ans, int(q.size()));        }        return ans;    }};

复制代码

Java 代码

class Solution {    public int lengthOfLongestSubstring(String s) {        char[] cnt = new char[128];        LinkedList<Character> q = new LinkedList<Character>();        int ans = 0;        for (int i = 0; i < s.length(); i++) {            q.add(s.charAt(i));            cnt[s.charAt(i)]++;            while (cnt[s.charAt(i)] > 1) {                char frontC = q.pollFirst();                cnt[frontC]--;            }            ans = Math.max(ans, q.size());        }        return ans;    }}

复制代码

题目链接: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

我是编程熊，持续输出 LeetCode 题解、大厂面试、大厂靠谱点对点内推 相关内容，关注''一只编程熊"，获取信息吧！

欢迎『关注』、『点赞』、、『转发』支持~

发布于: 19 小时前阅读数: 5

原文链接:【http://xie.infoq.cn/article/940baafef2956f8207d689c90】。文章转载请联系作者。

一只编程熊

关注

公众号: 一只编程熊 2021.06.30 加入

公众号: 一只编程熊；字节、旷视前员工，ACM金牌

发布

暂无评论

创作场景

【LeetCode 每日一题 Day 3】3. 无重复字符的最长子串

题意

题解

C++代码

Java 代码

一只编程熊

评论