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

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

最长无重复子串【MID】

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

题干

在这里插入图片描述

解题思路

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

双指针标识数组或字符串的位置，右指针可以理解为放大窗口指针，左指针可以理解为缩小窗口指针
定义一个set用来存储元素位置对应的值
右指针先行，如果一直无重复就一直开拓窗口并更新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;
    }
}