算法练习：无重复字符的最长子串（滑动窗口）

一.前言

今天遇到了这种找出无重复字符的最长子串的算法题，小编思来想去依旧没有想到有什么好方法，直到看到了大佬的算法，极为震撼，想写篇博客，记录下来。

题目如下：给出一组字符串，如 s = “ adsjkhf ”，返回值为 7，s = “abb”，返回值为 2，s = “aab”，返回值为 2。请判断此字符串中无重复字符的最长子串。

二.补充

Java HashMap 中的方法：

get() 方法获取指定 key 对应对 value：map.get(key)

put() 方法将指定的键/值对插入到 HashMap 中：map.put(key,value)

containsKey()方法如果 map 中存在指定的 key 对应的映射关系返回 true，否则返回 false。

三.题解

本题主要通过滑动窗口的思想解决。那么什么是滑动窗口呢？其实就是类似于两个前后指针，两个指针不断向后移，我们只关注指针中间的数，最后返回指针中间的元素的个数。

(1) 分析

我们先定义一个 map 容器用于存放字符串中的每个字符，然后从字符串的第一个字符 a 开始（ i = 0 ）开始找，此时 map 里面是没有这个元素的，因此我们把 a 存放进 map 中，继续执行此操作直到出现 map 中有相同的字符，此时只需把 left 指针指向相同元素的后一位，两个指针中间的部分就是不重复字符的子串，此时这个子串的长度就为 i - left + 1。我们只需要用这个方法往后看去（随着 i 增加，即后指针向后指去），寻找是否有比当前子串长度更大的，若遇到则将现在的长度替换即可。

注意：字符串可能是这样的 –> “ abbac”。按照我们的方法，会先将 ab 存入到我们的 map 当中，此时 left = 0，当 i=2 时，由于 map 中已经有 b，因此 left 将等于 get(b) + 1 = 2。随后 i 指针向后指去又遇到 map 已有元素 a，按照前面的算法，此刻 left = get(a) + 1 = 1,但实际上 left 不会变，仍然等于 2，因此在求 left 值时总应该取最大的那个。

(2) 代码详解


public int lengthOfLongestSubstring(String s) {

       int maxLen = 0;//记录最长的的无重复字符串的长度

        int left = 0;//前指针

        HashMap<Character,Integer> map = new HashMap<>();

        for (int i=0;i<s.length();i++){

            if (map.containsKey(s.charAt(i))){    //若map中有此元素则执行下面代码

                left = Math.max(left,map.get(s.charAt(i))+1);  //上面已经解释，此处应一直取较大的left

            }

            map.put(s.charAt(i),i);       //将s中的第i个元素存入map中

            maxLen = Math.max(maxLen,i -left + 1);  //maxLen即为两个指针中间的元素个数

        }

        return maxLen;

    }