专栏首页架构说无重复字符的最长子串

无重复字符的最长子串

一、描述

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

 输入: "abcabcbb"
 输出: 3
 解释: 最长子串是 "abc"

同类:给一个字符串str,找到str中最长的连续子串(不区分大小写),返回其长度。

思考 60秒 。。。

思考 60秒 。。。

二、思路

  • 如何判断一个子串没有重复字符--->遍历过程中 判断[start,i] 没有重复记录 是统计个数做到
  • 如果重复多次,舍去最早出现的。
  • 这就是滑动窗口。

三、代码

 class Solution
 {
 public:
     //看到这个题目 输入: "bbbbb" ,我马上想到map 统计每个字符个数,
     //这里让统计key 可能是任意字符长度子串 "pwwkew" 该怎么办
     //说明key 如果是string 性能可能下降。必须字符作为key。
     // 8 ms
     //测试: aa->1
     int lengthOfLongestSubstring(string s)
     {
         int result = 0;
         vector<int> data(128, -1);
         //ASCII码表里字符总共有128个 ASCII码的大小规则:0~9<A~Z<a~z。,用每个字符作为key,永远不可能越界。
         //如果重复出现。舍去后面字符重新计算。
         int start = 0;
 
         for (int i = 0; i < s.size(); i++)
         {
             char temp = s[i];
             //位置关系 [0 ...start ...i)
             if (data[temp] >= start)
             {
                 //如果有重复部分,移动掉前缀重复,重新开始计算。
                 //移动窗口开始位置。
                 start = data[temp] + 1;
             }
             data[temp] = i;
             //如果不重复,理想情况,移动窗口结束位置。
             result = max(result, i - start + 1);
         }
 
         return result;
     }
 };
 /**
  * @param s: a string
  * @return: an integer
  */
 func lengthOfLongestSubstring (s string) int {
     // write your code here
 
     var result int =0
     var start int  =0
 
     hash:=make([]int,128)//默认初始化为0,这里初始化为-1
     for i:=0;i<128;i++{
         hash[i] =-1
 }
 
     for i:=0;i<len(s);i++{
         //判断是否重复
 
         end:=s[i]
         if(hash[end] >=start) {
             start =hash[end]+1
         }
         hash[end]=i //end-->i
 
         result = max(result,i-start+1)
 }
 
     return result
 
 }
 
 func max(i,j int)int{
     if i>j{
         return i
     }else{
         return j
 }
 }

分享最实用的经验 , 希望每一位来访的朋友都能有所收获!

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode第513题-找树左下角的值

    Given a binary tree, find the left most value in the last row of the tree.

    程序员小王
  • leetcode-太平洋大西洋水流问题

    水流既可以流动到“太平洋"意思是:从任意位置出发,能达到 大陆的左边界和上边界 就可以。(~ ~ ~)

    程序员小王
  • Saga分布式事务解决方案与实践

    我先介绍一下我自己,我叫姜宁,来自于华为开源研究中心,现在负责的是ServiceComb这个开源项目。ServiceComb这个项目已经进到Apache孵化,应...

    程序员小王
  • 蓝桥杯 试题 基础练习 报时助手

    用户7727433
  • JavaProblem之hashCode详解

    一、HashCode简介 1.1、什么是Hash和Hash表   要想清楚hashCode就要先清楚知道什么是Hash   1)Hash ? ?  hash是...

    用户1195962
  • 数字在排序数组中出现的次数

    题目:统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输出4. 找到排序数组中...

    猿人谷
  • Opos每周一题(兔哥哥儿摘苹果)

    非常高兴又可以多一块内容了。这里非常感谢“Oops”学弟,特别说明本部分是小白的学弟“Oops”同学独家赞助。也欢迎更多的小伙伴来分享你的学习成果

    小白学视觉
  • Java程序员月薪三万,需要技术达到什么水平?

    最近跟朋友在一起聚会的时候,提了一个问题,说Java程序员如何能月薪达到二万,技术水平需要达到什么程度?人回答说这只能是大企业或者互联网企业工程师才能拿到。也许...

    Java编程指南
  • FXForms,自动生成iOS表单

    1.简介 FXForms是一个简单的表单提交框架,他的作者是鼎鼎大名的 Nick Lockwood,你也许听说过他的其他的一些框架,比如 iCarousel. ...

    ios122
  • 一文看懂HashMap扩容为什么是2的n次幂

    HashMap是Java中的集合类,是存放键值对形式的数据(Key和Value),例如QQ账号和QQ密码,QQ账号就是Key而密码则是Value。如下图所示(假...

    大猫的Java笔记

扫码关注云+社区

领取腾讯云代金券