博客

本文主要解释leetcode 的第三题：无重复字符的最长子串

原链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

 虽然原题也有答解，但由于个人理解起来较为困难所以在这里记录下理解过程，也探究一下滑动窗口的思想

以下是代码：

String s = "applepie";

        Map<Character,Integer> map = new HashMap<>();
        int answer = 0;
        char c;
        int length = s.length();
        for (int start = 0,end = 0 ;end<length;end++){
            c = s.charAt(end);
            if(map.containsKey(c)){
                start = Math.max(start,map.get(c));
            }
            answer = Math.max(end-start+1,answer);
            map.put(c,end+1);
        }

        System.out.println(answer);
    }

滑动窗口的时间复杂度只是O(n)，只用遍历一次字符串就能得到最长的不重复子串。

最长不重复子串：在一个字符串整体中截取一个小子串，这个字串中的任何字符不能有重复

需要定义以下数据结构

answer：存放最长子串的个数， 在每次循环都进行更新

map：存放每个字符的下一个字符位置，由于是个map，所以每个字符只会出现一次

end：循环变量，也是滑动窗口的尾

start：滑动窗口的头，当窗口内出现重复的值时（也就是map中含有窗口某个值的数据），把map中的值（也就是那个字符下一个位置）设置到头部，因为字符串中不能有两个相同的单词，所以会从相同字符哪里进行截取）

          并且这里用start = Math.max(start,map.get(c));的意思是防止头部向回滑动，比如abba的情况，在end到达最后一个a的时候吗，这时本来头在第二个b，如果直接是start = map.get(c); 那么头部反而会滑动到第一个a的下一个字符也就是第一个b，导致结果出现问题。滑动窗口一定是单向的

 总结

定义头和尾，尾按序遍历，遍历之后把值和对应的下标+1放入map中。

当要向map中存放一个相同的数据时，就该移动头的位置了，把头移动到map中对应键的值的位置