力扣3-无重复字符的最长子串

简介: 力扣3-无重复字符的最长子串

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

题目要求

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

示例一

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例二

输入: s = “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例三

输入: s = “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。

请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

  • 提示:
  • 0 <= s.length <= 54
  • s 由英文字母、数字、符号和空格组成

解题

滑动窗口

  1. 最开始的时候
  1. 创建START、END指向字符串最前端的位置
  2. 创建LENTH记录当前长度
  3. 创建RESULT记录无重复字符的最长字串长度
  1. 使用循环,向后移动END
  1. 检查END指向的新字符是否与字串内的字符重复
  • 如果重复,移动START到重复字符的下一个位置
  • 如果不重复,则不移动
  1. 重新计算LENTH=END-START+1
  2. 对比当前LENTG和已记录的RESULT,取较大值为新RESULT

分析图中过程:

  1. 上图中,左侧三步中均无重复字符
  1. START停留在原地不动,END++
  1. 右侧第一幅图中,END指向的新字符A与子串中字符A重复
  1. START移动到原子串中字符A的下一个位置,即字符B所在位置
  2. LENTH=3;
  3. RESULT=3;
  1. 右侧第二幅图中,END指向的新字符C与子串中字符C重复
  1. START移动到原子串中字符C的下一个位置,即字符A所在位置
  2. LENTH=2
  3. RESULT=3

敲代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        for (int index = 0; index < s.size(); index++)
        {
            end = index;
            for (int i = start; i < end; i++)
            {
                if (s[i] == s[end])
                {
                    start = i + 1;
                    //及时跳出
                    break;
                }
            }
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果

执行用时: 8 ms

内存消耗: 6.7 MB

哈希表

思路与滑动窗口相同,不同的是查找重复元素的方式

  • 滑动窗口是用遍历字符串的方式
  • 哈希表是用容器自带的find方法

需要注意的是:

  1. 查找到重复元素后,要将表中记录的该元素的位置修改为最新位置
  2. 由于重新确定区间后,不清楚到底少了哪些元素,所以判断重复元素时,应确保该位置在START之后

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        unordered_map<char, int>mp;
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (mp.find(s[i]) != mp.end() && mp[s[i]] >= start)
            {
                start = mp[s[i]] + 1;
            }
            mp[s[i]] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果

执行用时: 20 ms

内存消耗: 8.1 MB

桶优化

判断是否出现过时,利用vector容器代替哈希表以优化时间

  • int[26]用于字母’a’-‘z’或’A’-‘Z’
  • int[128]用于ASCII码
  • int[256]用于扩展ASCII码

思路与前两种方法相同,不同的仍是检验重复的方法

  1. 每次移动END,都将END指向的字符转化为ASCII码对应的数字
  2. vector容器中对应的数字下标的值存储的是改数字最后出现的位置
  1. 如vec[2]=3,意思是ASCII码中值为2的字符,目前最后一次出现在字符串中的第4个字符的位置
  1. 判断END所指的字符在vector容器中存储的位置,是否大于START
  • 如果大于,则修改START,指向存储的位置的下一个位置
  • 否则,不操作START

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        vector<int>v(128, -1);
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (v[int(s[i])] >= start)
            {
                start = v[int(s[i])] + 1;
            }
            v[int(s[i])] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

运行结果

执行用时:8 ms, 在所有 C++ 提交中击败了88.74%的用户

内存消耗:7.4 MB, 在所有 C++ 提交中击败了79.74%的用户

总结

力扣给这道题的分类是中等,对新手来说很难,而且还用到了两个指针,虽然上面的代码中用的是下标访问的方式,不是严格的指针,但也不容易,建议就是多看看题解,多写几遍代码,对于容器和重载的一些方法,可以随时去cplusplus网站查阅,边刷题边巩固

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=26uneso59lnoo

目录
相关文章
|
12天前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
12天前
|
算法
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
41 0
|
12天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
|
12天前
|
存储 算法 Go
LeetCode 第三题: 无重复字符的最长子串
  给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
|
12天前
【Leetcode 2707】字符串中的额外字符 —— 动态规划
1. 状态定义:把`s[i−1]`当做是额外字符,`d[i] = d[i−1] + 1` 2. 状态转移方程:遍历所有的`j(j∈[0,i−1])`,如果子字符串`s[j...i−1]`存在于`dictionary`中,那么`d[i] = min d[j] 3. 初始状态`d[0] = 0`,最终答案为`d[n]`
|
12天前
leetcode:3. 无重复字符的最长子串
leetcode:3. 无重复字符的最长子串
18 0
|
12天前
|
算法
leetcode:387. 字符串中的第一个唯一字符
leetcode:387. 字符串中的第一个唯一字符
15 0
|
12天前
|
存储 索引
力扣1445 连续字符
力扣1445 连续字符
23 0
|
2天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
7 1