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

一.算法题

• 题目

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",是子序列,而不是子串

三.暴力解决方案

3.1 思路

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

3.2 算法

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

3.3 复杂的分析

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

3.4 参考代码