Loading...
墨滴

编程熊

2021/07/02  阅读:63  主题:橙心

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

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

题意

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

示例

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

题解

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

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

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

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

时间复杂度:

空间复杂度:

知识点总结: 滑动窗口

C++代码

class Solution {
public:
    queue<char> q;
    int lengthOfLongestSubstring(string s) {
        vector<charcnt(1280);
        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题解、大厂面试、大厂靠谱点对点内推 相关内容,关注''一只编程熊",获取信息吧。

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

编程熊

2021/07/02  阅读:63  主题:橙心

作者介绍

编程熊

公众号: 编程熊