前言

如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对LeetCode。这里我会记录刷leetcode的学习和思考的过程，如果和leetcode官方解题有雷同，那是当然会有的啦。我会在记录的同时配以图文解释，如果对大家有帮助，那就再好不过了。

题目

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

示例：（具体可在leetcode中查看）

input：abcabcbb

output：3

思路

暴力破解

首先我们需要i和j用两层嵌套循环来遍历所有子串。对于每个子串，我们需要判断子串中是否有重复，也就是需要遍历该子串，那么这个时间复杂度是。

滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。i和j代表下标，表示数组中到的元素。开闭可自定义，但一般前闭后开。在此题中，如果从到的子字符串没有重复，那么我们只需要检查对应的字符是否已经在中。我们用HashSet构造一个滑动窗口，将当前无重复的字符存在HashSet中。如果在hashset中，则++，子串长-1，ans不动；如果不在hashset中，则++，子串长+1，ans更新。此题只需要用更大的ans改写之前的ans就行，不需要输出最长的无重复子串是什么，用hashset没问题。附代码和图解如下。时间复杂度为。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int i = 0;
        int j = 0;
        int ans = 0;
        while(i<s.length() && j<s.length()){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                j += 1;
                ans = Math.max(ans, set.size());
            }else{
                set.remove(s.charAt(i));
                i += 1;
            }
        }
        return ans;
    }
}

leetcode 3｜滑动窗口解法

优化的滑动窗口

上面滑动窗口的方法要不停的增加元素和移除元素，虽然我们已经利用hashset使增加元素和移除元素的时间复杂度尽可能低，但是我们还有方法可以加速。如果我们遇到一个重复的元素，则可直接跳转到当前子串中重复元素的后一位，这在重复元素在子串中间时特别高效。优化的滑动窗口利用hashmap存储当前最长子串，并且不需要删除元素。当j增加一位的时候，我们检查是否在hashmap中，并查找map中对应的value值即可判断是否重复，如果重复，则跳转到value+1。这里的一个关键问题是，我们不删除hashmap中的元素，如何判断遇到的新元素是否已经在当前最长子串中？这里非常欣赏leetcode官网的解答，代码如下。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
                //关键步骤，hashmap如何判断是否有重复。
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

这句代码的意思是如果在map中，获得对应的value值，如果value值小于当前i，则表示并未重复。大家可以好好体会这段代码，图解见下图。

leetcode 3｜优化的滑动窗口

小结

这是我刚开始在leetcode上刷题，所以参考了leetcode的官方解法，时间有限就不看更多解法了。这里官方解法中的hashmap解法个人认为非常精彩，对于实现滑动窗口有非常好的优化。

结尾

如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的图文，请点喜欢~*我是蓝白绛，感谢你的阅读！