leetcode刷题之无重复字符的最长子串

无重复字符的最长子串

题目描述解题思路暴力代码优化代码反思

题目描述

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

示例1 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例2 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例3 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

暴力解法就是遍历完所有的子字符串，然后找出子字符串中没有重字符的最长的，返回长度。这种具体是用$i$从字符串第一个元素开始，以第$i$个元素为开头的子字符串依次获取到，并输入到一个判断判断字符串是否有重复字符的函数中，返回判断结果。这样遍历到字符串中最后一个元素。就可以找到最长的无重复子串。这里的判断函数里面就是字串里面字符两两相比较，有相同的就break，返回结果。时间复杂度就是$n^3$优化：主要在优化字串的重复上，上一步暴力，当在$i$开头的子串进行遍历时，这时第$j$个字符为止，这$i到j$中没有重复的字符，进行$j+1$判断时，第$j+1$个字符与$i到j$之中重复，那么$i$开头的就完了，继续遍历$i+1$时，这个时候，暴力解法就把$j$重置为初始值，忽略了其实之前已经判断了$i到j$之间的字符。这里我们需要做的就是在开始遍历$i+1$子串时，$j$可以直接从上一步判断结束的$j$值开始走。

滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。

暴力代码

package com.leetCode.lengthOfLongestSubstring; import java.util.HashSet; import java.util.HashMap; public class Solution { public int lengthOfLongestSubstring(String s) { HashSet<Character> substr = new HashSet<Character>(); int maxlen = 0; for(int i=0;i<s.length();++i) { substr.clear(); for(int j=i;j<s.length();++j) { if(false==substr.contains(s.charAt(j))) { substr.add(s.charAt(j)); }else{ break; } } if(substr.size()>maxlen){ maxlen = substr.size(); } return maxlen; } }

结果如下：

优化代码

class Solution { public int lengthOfLongestSubstring(String s) { HashSet<Character> substr = new HashSet<Character>(); int maxlen = 0; for(int i=0;i<s.length();++i) { for(int j=i+substr.size();j<s.length();++j) { if(false==substr.contains(s.charAt(j))) { substr.add(s.charAt(j)); }else{ break; } } if(substr.size()>maxlen){ maxlen = substr.size(); } substr.remove(s.charAt(i)); } return maxlen; } }

结果如下：

反思

这里的解法其实还可以优化，参考KMP算法，但是我还没理清楚下一步该怎么减少比较次数。