博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode-3:Longest Substring Without Repeating Characters
阅读量:6623 次
发布时间:2019-06-25

本文共 603 字,大约阅读时间需要 2 分钟。

描述:给一个字符串s,找到它的最长子串(无任何字符重复)substring的长度。

举例:

    Input: "abcabcbb"

    Output: 3

    Explanation: The answer is "abc", which the length is 3.

思路:

    我的做法是从左至右扫描,设repeat[c],记录字符c上一次在字符串s中出现的位置。假设现在正在扫描s[j]字符,而之前已经记录s[i,j-1]都未出现任何重复字符。假设检测到s[j]上一次出现的位置repeat[j]在区间[i,j-1]内,那么可以截取子串s[i,j-1]并与当前smax做优选。接着我们可以从repeat[j]开始,更新区间为s[repeat[j]+1,j]并继续向后扫描处理。

    官方的思路其实跟我的一致,不过叙述上有所差别。它提出了滑动窗口SliddingWindow的概念,并且使用HashSet存储窗口P[i,j)内的所有未重复字符。当发现s[j]在HashSet中重复时就要动态更新窗口下限i,尽可能大地向右滑动。详见:https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/

 

 

转载于:https://www.cnblogs.com/Jackie-Snow/p/9531958.html

你可能感兴趣的文章
Oracle 再向 Apache NetBeans 捐赠 150 万行代码
查看>>
云栖大会·南京峰会落下帷幕,阿里云都干了些什么?
查看>>
意外与健康问题不断,放眼未来的特斯拉正在压榨员工?
查看>>
rsync+sersync实现服务器文件同步
查看>>
一场由AI引发的GPU血案,AMD还有机会吗?
查看>>
Mockito教程
查看>>
Ubuntu 16.04安装微信
查看>>
「镁客·请讲」竹间智能简仁贤:基于情绪识别打造对话式AI,推进机器人融入商业...
查看>>
VR全景看年评!PConline年度评测盛典等你来体验
查看>>
一汽解放智能卡车成功完成高速公路,或于2015年实现全自动驾驶产品开发
查看>>
区块链基础1
查看>>
锐捷伴你游之锐捷助力重庆大融城智慧Wi-Fi 10万粉丝
查看>>
你通过区块链获得免费的东西
查看>>
开始学习设计模式
查看>>
shell脚本-简单的添加用户并统计总用户数
查看>>
VR体验的“第一印象”正在崩塌,追踪定位技术会是救命稻草吗?
查看>>
Python【7】-数据分析准备
查看>>
Scrapy研究探索(七)——如何防止被ban之策略大集合
查看>>
关于const char*和char*、const char** 和char** 赋值问题
查看>>
JAVA入门[5]-初步搭建SpringMVC站点
查看>>