1.题目:无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
总结:上述解题思路忽略了空格字符串的情况,存在问题.
时间窗移动原理
/**
* 思路一:
*
* 1.把字符串转换为字符数组
* 2.把字符串逐个放入set集合(set),同时记录放入集合的数量(j)
* 2.如果set集合长度和放入数量不符,记录该长度(l),清空set集合,把j设置为0,放入刚才放入的值,继续循环
* 3.如果继续出现上述清空,和上面记录的长度进行对比,小于清空继续,大于更新记录长度
*
* 时间复杂度:T(N) 空间复杂度:O(1)
*
* 测试情况:不通过
*
* 总结分析:
*
* 1.没有考虑到空格字符串的情况
*/
public int lengthOfLongestSubstring1(String s) {
char [] chars = s.toCharArray();
Set set = new HashSet();
int l=0;
for (int i=0,j=0;i<chars.length;i++){
set.add(chars[i]);
j++;
if (set.size()<j){
l = Math.max(set.size(),l);
set.clear();
j = 1;
set.add(chars[i]);
}
}
return l;
}
/**
* 思路二: 滑动窗口
*
* 1.定义一个map集合(map),用于存储字符值和位置,key为字符,value为字符位置加1
* 2.定义一个变量ans,用于记录时间窗最大长度
* 3.定义时间窗起点start和时间窗结束点end
* 4.然后把end向右滑动,最大长度为(end-start+1),如果map集合中存在该元素,说明遇到了重复的元素
* 4.1.记录时间窗最大值ans
* 4.2.移动时间窗start到重复元素第一个之后的位置
* 5.继续滑动,直到j=字符串长度
*
*/
public int lengthOfLongestSubstring2(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int end = 0, start = 0; end < n; end++) {
char alpha = s.charAt(end);
if (map.containsKey(alpha)) {
start = Math.max(map.get(alpha), start);
}
ans = Math.max(ans, end - start + 1);
map.put(s.charAt(end), end + 1);
}
return ans;
}
在做这道题目的过程中,没有考虑到空格字符串的情况,这是基础不扎实导致的,null/“”/“ “,这三个还是有很大的区别的,如果大家也遇到和我一样的问题,可以当做是一个教训。
还有就是滑动窗口,这个理解比较麻烦,最好可以看我上面画的那种图,或者你可以自己画一个出来,滑动窗口是一个常用的办法,我们要深入理解。记得在有一次做限流的时候也用到了滑动窗口的概念。
▌本文来源:share猿