BAT面试算法进阶(3)-无重复字符的最长子串

一.算法题

题目

Given a string, find the length of the longest substring without repeating characters.

Example

  • Given "abcabcbb", the answer is "abc", which the length is 3.
  • Given "bbbbb", the answer is "b", with the length of 1.
  • Given "pwwkew", the answer is "wke", with the length of
  • Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

二.算法题解读

题目大意:给定一个字符串,找出不含有重复字符的最长子串的长度

解读Example

  • 给定"abcabcbb",没有重复字符的最长子串是"abc",那么长度就是3
  • 给定"bbbbb",最长子串就是"b",长度就是1
  • 给定pwwkew,最长子串就是"wke",长度为3,
  • 注意,必须是一个子串."pwke",是子序列,而不是子串

三.暴力查找解决方案

思路

逐个检查所有的子字符串,看它是否不含有重复字符

算法

为了枚举给定字符串的所有子字符串,我们需要枚举它们开始和结束的索引,假如开始和结束的索引分别是i和j.那么我们有0<=i<=j<=n.因此,使用i从0到n-1以及j从i+1到n这2个嵌套循环.我们就可以遍历出a的所有子字符串.

四.复杂度分析

  • 时间复杂度:o(n3);
  • 空间复杂度:o(min(n,m));

五.参考代码

原文发布于微信公众号 - HelloCode开发者学习平台(HellCode_CC)

原文发表时间:2018-08-11

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

第十七天 集合-Collection&amp;增强for&amp;迭代器【悟空教程】

出现意义:面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就对对象进行存储,集合就是存储对象最常用的一种方式。

1102
来自专栏CSDN技术头条

在下函数式编程,有何贵干?

本文简单介绍了一下函数式编程的各种基本特性,希望能够对于准备使用函数式编程的人起到一定入门作用。 ? 函数式编程,一个一直以来都酷,很酷,非常酷的名词。虽然诞生...

1977
来自专栏计算机视觉与深度学习基础

java在acm中大数运算教程

import java.io.*; import java.util.*; public class Main { public static void ...

2089
来自专栏机器学习入门

LWC 51:681. Next Closest Time

LWC 51:681. Next Closest Time 传送门:681. Next Closest Time Problem: Given a time ...

2596
来自专栏别先生

Map集合遍历的四种方式理解和简单使用

~Map集合是键值对形式存储值的,所以遍历Map集合无非就是获取键和值,根据实际需求,进行获取键和值 1:无非就是通过map.keySet()获取到值,然后根据...

2146
来自专栏java一日一条

Java ArrayList的不同排序方法

由于其功能性和灵活性,ArrayList是 Java 集合框架中使用最为普遍的集合类之一。ArrayList 是一种 List 实现,它的内部用一个动态数组来存...

1442
来自专栏Java学习网

Java面试题系列之基础部分(五)——每天学5个问题

Java基础部分学习的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语法,集合的语法,io的语法,虚拟机方面的语法,这些都是最基...

21210
来自专栏曾大稳的博客

c++基础语法

注意:在开发过程中,cpp或者c会被编译为dll或者so供其调用者使用,一般把public的函数定义到h文件,不然调用者都不知道有哪些函数。

1023
来自专栏向治洪

数据结构之串

基本概念 串(string)是由零个或多个字符组成的有限序列,又名叫字符串。形如s="a,b,c.."。ai(1 ≤ i ≤ n)可以是字母、数字或其他字符,i...

2768
来自专栏java技术学习之道

java集合类详解

1456

扫码关注云+社区

领取腾讯云代金券