【力扣】3.无重复字符的最长子串

一、题目

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

二、示例

示例1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:

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

三、分析

这道题看起来很容易的样子，但是官方将它的难度定义在了中等一个不上不下的难度，说明其中还是会有一些想不到的点，会被忽略。

拿到这道题第一想法就是窗口滑动。将最大的窗口进行返回，因此我们可以先将字符串变成数组，好方便我们进行窗口移动，移动的轨道有了，就需要一个窗口。定义一个窗口左值，以及窗口的右值。窗口的右值可以是遍历的轨道的下标。我们还需要一个返回的最大长度值，以及当前窗口的长度值，用来比较每次的移动后得到的窗口长度。看起来没有问题，实际上还缺少一个走过的轨迹。加一个已经走过的轨迹集合。然后就可以进行移动窗口了。

四、实现

public class LengthOfLongestSubstring {
    
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int left = 0;
        int max = 0;
        int tempLength = 0;
        Map<Character, Integer> lujing = new HashMap<>();
        for (int right = 0; right < chars.length; right++) {
            char c = chars[right];
            Integer index = lujing.get(c);
            lujing.put(c, right);
            // 如果不存在，或是存在的不在当前的区间内，进行添加临时长度
            if (index == null || index < left) {
                tempLength = right - left + 1;
                continue;
            }
            // 如果临时长度大于当前最大，更新最大值
            if (tempLength > max) {
                max = tempLength;
            }

            // 临时长度变化
            tempLength = right - index;
            // 向前移动一位
            left = index + 1;
        }
        if (tempLength > max) {
            return tempLength;
        }
        return max;
    }
}

首先先将字符串变成数组。方便我们进行滑动。lujing这个变量是走过的路径都会记录下来，用来查找是否是出现重复的。进行遍历这个数组，当前的路是否在当前的窗口里面，如果不在的话，窗口可以进行增加。存在的话，就要进行和最大的路径比较，如果比最大的还大的话。更新这个值到最大值里面。然后将临时的长度重新计算。并把左窗口的值进行前移一位。

五、致谢

感谢每一位读者花费您的宝贵时间认真阅读我的一点也不华丽的文章。