leetcode--无重复字符的最长子串
创始人
2025-05-30 17:44:39
0次

前言

今天做题做到这道题看到一种很神奇的做法，想写这一篇博客记录一下具体的思路过程

题目描述

我们先来看题目的描述
图1
我们要注意一下这个示例三的描述，题目说的是要求子串，子串在这个原字符串中应该是连续的,所以对于“pwwkew”这个字符串的子串就应该是wke而并非是pwke。

解题思路

这道题我们的解题思路是“移动窗口”的方法，从字符串首个元素开始遍历，当出现重复字符的时候就把起点从首元素改为这个重复字符的位置，并把上一次从开始到找到第一个重复字符时的子串长度，以此类推，每次找到重复的字符就截断，把起点重设并记录该子串长度与前一次的子串长度比较。最后返回最大子串的长度。

变量设置

根据上述的解题思路来设置合适的变量。

result->最长子串长度
tail->存放找到的重复字符后一个元素的地址
head->用来遍历字符串的指针
p->从上一个子串的tail到head遍历判定是否有重复字符

代码分析

先来看代码

#include 
#include 
#include int lengthOfLongestSubstring(char* s) {int result = 0;char* tail = s, * head = s, * p;while (*head != '\0') {for (p = tail; p < head; p++) {if (*p == *head) {tail = p + 1;break;}}result = (head - tail + 1) > result ? (head - tail + 1) : result;head++;}return result;
}int main()
{char s[] = "abbcdeffff";int ret = lengthOfLongestSubstring(s);printf("%d", ret);return 0;
}

我们通过图来分析
图2
图3
图4
图5找上述的主体思路遍历完整个字符串即可找出字符串中最长子串的长度，在网上看到有对这种解法一个很形象的比喻：如同一只贪吃蛇（头）与蜥蜴（尾）的组合体，外循环“向前吃”同时计算子串长度，当头遇到天敌（重复字符）时，内循环“断尾求生”（断尾处为子串内重复字符出现处），重复上述过程，直到“吃”完整条字符串！

就以上述代码为例，运行结果如下
图6
这个子串就是abcdef。
以上就是这道题的一整个解法思路以及代码实现了，如有出入，欢迎指正。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【数据结构练习】二叉树练习

下一篇：IDEA如何打开Java项目（案例学习）

相关内容

热门资讯

王凤英入职小鹏3年终获股权，此... 5月7日消息，小鹏汽车披露的监管及年报信息显示，公司总裁王凤英已正式进入股东名册，入职小鹏3年后股权...
五块钱红酒卖断货，便宜红酒为何... 最近一段时间，中国的酒类消费市场可以说是显得格外奇怪，一方面，各种高端酒特别是白酒的消费量出现了明显...
财联社C50风向指数调查：4月... 财联社5月8日讯（记者 夏淑媛）新一期财联社“C50风向指数”结果显示，市场机构对4月新增人民币贷款...
央视硬刚国际足联拒掏20亿，背... 作者| 史大郎&猫哥 来源| 是史大郎&大猫财经Pro 央视这次太刚了，离世界杯开幕还有1个月，死活...
新CEO上任直接放大招！Air... 快科技5月8日消息，苹果即将上任的CEO John Ternus对未来一系列新产品充满信心，称这些设...
“特朗普拟邀英伟达、波音等CE... 据路透社当地时间5月7日报道，特朗普政府正邀请英伟达、苹果、埃克森美孚、波音等大公司首席执行官，于下...
世界杯，还能看到直播吗？ 2026年美加墨世界杯距离开幕，仅剩一个多月时间。多方信息显示，中央广播电视总台（以下简称“央视”）...
机构警告AI芯片热潮风险，超威... 5月7日，据央视财经，隔夜超威半导体公司(AMD)股价飙升近19%，带动AI芯片热潮持续升温。AMD...
银行员工转走储户1800万最新... 银行员工转走储户1800万最新进展：2名储户已收到银行全部款项
原创 中... 1994年，安徽省的经济格局曾发生过一次戏剧性的转折。在那一年，一座名为安庆的城市，其国内生产总值（...
昆都仑区：政策“蓄力”消费焕新 “一台5000多元的空调，叠加‘国补’和商场的以旧换新活动，能优惠1000元左右，旧机还能免费上门拆...
乐悦置业竞得佛山顺德乐从镇一商... 观点网讯：5月6日，佛山市顺德区乐从镇一商业地块成功出让，由广东省乐悦置业有限公司竞得，乐从南区·邻...
原创 亦... 《爱情没有神话》这部剧，一开始的命运颇为多舛，经历了几次撤档的波折后，终于在观众面前亮相，但其首播的...
美联储34年最大分歧叠加油价飙... 美联储按预期维持利率不变，但内部出现34年来最严重分歧，叠加布油创2022年6月以来新高，美债遭抛售...
支付宝消费券回收后，资金是否支... 摘要： 支付宝消费券回收变现后，资金能否直接转入信用卡？本文解答到账方式的相关规则，帮助用户了解资金...
中医介绍5个化痰穴位！收藏这篇... 很多人忽略了“痰”的危害，觉得咳几下就没事，殊不知，肺里的痰长期堆积，只会一步步加重身体负担。 中医...
黄金平台“杰我睿”涉嫌经济犯罪... 红星资本局5月7日消息，深圳水贝知名金店“杰我睿”兑付困难事件有了新进展。日前，深圳市公安局罗湖分局...
多地出台购房新政促楼市升温 记... 今年的“五一”假期，伴随着多个城市楼市新政密集落地，在叠加市场信心持续修复的作用下，房地产市场热度持...
谁是五一“吸金王”？这5座城市... 来源：市场资讯 （来源：21城市观） 哪座城市成为“五一”假期的大赢家？ 图源：摄图网 作者｜赵晓...
“低招低裁”格局稳固劳动力市场... 智通财经APP获悉，美国上周初请失业金人数在经历前一周回落至近几十年来最低水平后出现小幅反弹，表明尽...