【算法训练-字符串】一 最长无重复子串

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是最长无重复子串或最长无重复子数组，这类题目出现频率还是很高的。

最长无重复子串【MID】

先来看字符串数据结构的题目

题干

解题思路

整体目标就是获取最大的无重复滑动窗口

1. 双指针标识数组或字符串的位置，右指针可以理解为放大窗口指针，左指针可以理解为缩小窗口指针
2. 定义一个set用来存储元素位置对应的值
3. 右指针先行，如果一直无重复就一直开拓窗口并更新max值，否则移动左指针缩小窗口，直到将重复值缩到窗口以外。

如下图所示：

代码实现

基本数据结构：字符串
辅助数据结构：哈希表
算法：迭代
技巧：双指针、滑动窗口

class Solution {public int lengthOfLongestSubstring(String s) {// 1 判断入参是否为空列表if (s.length() == 0) {return 0;}// 2 定义返回结果最大值和左右指针以及滑动窗口集合int max = 0;int left = 0;int right = 0;Set<Character> set = new HashSet<>();// 3 滑动窗口移动并在无重复时计算最大值while (left < s.length() && right < s.length()) {// 1 无重复，右指针继续移动，重新计算最大值if (!set.contains(s.charAt(right))) {set.add(s.charAt(right++));max = Math.max(max, right - left);} else {// 2 有重复，左指针继续移动，直到将重复元素移出集合set.remove(s.charAt(left++));}}return max;}
}

复杂度分析

时间复杂度为O（N），因为遍历了字符串；空间复杂度为O（N），借助了HashSet的存储空间