从最大子串到窗口滑动算法，我终于明白了为什么大多数搞算法的人头发会少了！

头发总在那么不经意间流逝。

今天忘忧跟大家一起搞定leetcode第三题，无重复字符的最长子串。

题目描述

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

示例 1:

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

示例2:

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

示例3:

• 输入: “pwwkew”
• 输出: 3
• 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。

思路一（暴力法）

暴力法：没有暴力**不了的算法，如果有，那说明你不够暴力。

对字符串的每一个字符进行遍历。

1. 声明两个索引，其中一个索引 i 标示当前匹配的开始位置的索引，另一个索引 j 标示当前匹配的位置。
2. 判断字符串第 j 个位置的字符是否被[i, j)区间的字符所包含。如果包含，记录下索引 i 和索引 j 的差值作为当前遍历到的无重复元素的子串的长度， 并使索引 i 右移，j = i + 1,重复步骤2如果不包含，使 j 右移一位，重复步骤2
3. 从所有子串长度中选取最大值作为返回结果。

具体代码实现如下：

/**
 * 暴力解法，获取最长的无重复的子串的长度
 * @param s 输入的字符串
 * @return 最大子串长度
 * 公众号：算法之灵魂拷问
 */
public static int lengthOfLongestSubstring(String s) {
    int length = s.length();
    int maxSubStrLength = 0;
    //i标记起始位置
    for (int i = 0; i < length; i++) {
        //j标记当前判断的位置
        for (int j = i; j < length; j++) {
            boolean flog = false;
            //判断字符串的[i, j - 1]的区间内有无跟第i个字符相同的字符
            for (int k = i; k < j; k++) {
                if(s.charAt(k) == s.charAt(j)){
                    flog = true;
                    break;
                }
            }
            //如果字符串的[i, j - 1]的区间内有跟第i个字符相同的字符
            if(flog){
                //当前所遍历的最大长度为之前的最大长度或者(j - i)中的最大值
                maxSubStrLength = Math.max(maxSubStrLength, j - i);
                break;
            }else{
                //如果不存在，当前所遍历的最大长度为之前的最大长度或者(j - i + 1)中的最大值
                //其中，加的1即为第i个元素
                maxSubStrLength = Math.max(maxSubStrLength, j - i + 1);
            }
        }
    }
    return maxSubStrLength;
}

解析：

暴力解法固然可以得到最终的结果，但是暴力解法的时间复杂度为O(n ^ 3)， 运行效率是相当低的，那么有没有更好的方式呢？

思路二（滑动窗口法）

话不多说，直接上图！

滑动窗口法代码实现：

/**
 * 滑动窗口法
 * @param s 输入的字符串
 * @return 字符串最长无重复字串的长度
 * 公众号：算法之灵魂拷问
 */
public static int lengthOfLongestSubstring1(String s) {
    int length = s.length();
    if(length <= 1){
        return length;
    }
    //滑动窗口的右侧位置
    int right = 0;
    //滑动窗口的左侧位置
    int left = 0;
    //当前匹配到的最大子串长度
    int maxSubStrLength = 0;
    //窗口
    Set<Character> set = new HashSet<>(length);
    //遍历
    while(right < length){
        //如果窗口中包含即将划入窗口的元素
        if(set.contains(s.charAt(right))){
            //将窗口最左侧的元素移除
            set.remove(s.charAt(left++));
        }else{
            //如果窗口中不包含即将划入窗口的元素，那么将元素划入窗口
            set.add(s.charAt(right));
            //更新最大字串长度
            maxSubStrLength = Math.max(maxSubStrLength, set.size());
            //窗口右侧标记加一
            right++;
        }
    }
    return maxSubStrLength;
}

滑动窗口算法简介

滑动窗口算法，常用于解决一些字符串的字串，连续n个数的最大和，最小和等问题。
通过两个坐标（一般往右滑动的都是左闭右开）的方式，虚拟出一个固定大小或者动态大小的窗口，有效的节省了循环的次数，将原本的多次循环，循环嵌套等暴力解法的时间复杂度降低到了O(n)的级别。

生硬的文字没啥感觉，如果觉得还没懂，多看几遍图解或者把疑惑评价或者私信给我，忘忧尝试着给大家解惑

结束语：准备种子,就收获果实;准备努力,就收获成功;准备今天,就收获明天。