大厂面试-好未来一面算法之求最长无重复子串长度

大厂面试-好未来一面算法之求最长无重复子串长度

本文学习目标或巩固的知识点

• 学习如何处理经典题目《最长无重复子串长度》
• 巩固滑动窗口

---

提前说明：算法题目来自力扣、牛客等等途径

🟢表示简单
🟡表示中等
🔴表示困难
🤮表示恶心

博主真实经历，该题近期在好未来教育集团一面有考察！！！！！！一般大厂面试的做题时间也就10-30分钟左右，如果不经常练习或者没掌握技巧很容易栽倒到一些容易的题上面，等回头看只有空悲切！！！！掌握技巧和算法敏感度很重要！！！！！

3. 无重复字符的最长子串🟡🟢

求一个字符串中的最长无重复子串长度。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

例1：

输入: abcdedafg
输出：5
1
2

解释：abcde这是一个最长的无重复子串，同理edafg也是。所以最长的无重复子串是5。

通过题目可知

1. 一个随机字符串
2. 没有时间和空间复杂度的要求
3. 可以套用滑动窗口公式

题解

该题目属于窗口不固定的一类滑动窗口题目。

模板：

for|while(遍历){
   //或 增大窗口
   while(判断){
     //缩小窗口
   }
   //或 增大窗口
}
1
2
3
4
5
6
7

本题我利用了LinkedList，方便处理最长无重复子串长度问题。pollFirst头部出队，offerLast尾部入队。如果队列中包含重复的元素就不断地从头部出队直到不包含为止。
（也可以使用HashSet+双指针解决）

public int longestStr(String str){
    if(str == null || str.length()==0){
        return 0;
    }
    char[] chars = str.toCharArray();
    int max = 0;
    LinkedList<Character> rst = new LinkedList<>();
    for(int i=0; i<chars.length; i++){
        char ch = chars[i];
        while (rst.contains(ch)){
            //队列头部 出队
            rst.pollFirst();
        }
        //队列尾部添加元素
        rst.offerLast(ch);
        max = Math.max(max,rst.size());
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

结果验证