一、问题描述
Given a string, find the length of the longest substring without repeating characters.
意思是给你一个字符串，找到没有重复字符的最长字串。
二、生词
duplicate adj /ˈdjuːplɪkeɪt/ 重复的
nest vt. /nest/ 嵌套
三、样例及说明
四、解题思路及代码
伪代码：
- 初始化int类型变量length,tempLength,start，分别表示最大长度、临时长度和字串开始下标；
- 循环遍历从下标为1开始的字符，判断字串中是否包含该字符，是的话临时长度+1，否则：判断临时长度与最大长度，如果临时长度大于最大长度，则更新最大长度的值；把临时长度置1，字符串开始下标置为i。
1 class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int length = 1;
4 int tempLength = 1;
5 int start = 0;
6 for(int i=1; i<s.length(); i++) {
7 String sub = s.substring(start,i);
8 String msg = s.charAt(i)+"";
9 if(!sub.contains(msg)){
10 tempLength++;
11 } else {
12 if(tempLength>length)
13 length=tempLength;
14 tempLength=1;
15 start=i;
16 }
17 }
18 return length;
19 }
20 }
一切都看似顺利，在提交的时候WA了，靠。。。看了solution后，我用字符串判断的思路写了以下代码，结果。。。TLE。。。。
1 class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int ans = 0;
4 for(int i=0; i < s.length(); i++) {
5 for(int j=i+1; j <=s.length(); j++) {
6 if(judge(s,i,j)) ans=Math.max(ans,j-i);
7 }
8 }
9 return ans;
10 }
11 public boolean judge(String s, int start, int end) {
12 String sub = s.substring(start,end) ;
13 for(int i=start; i < end; i++) {
14 if(sub.indexOf((s.charAt(i)+""))!=sub.lastIndexOf((s.charAt(i)+""))) return false;
15 }
16 return true ;
17 }
18 }
solution中用的是set容器来判断是否有重复元素，于是修改代码：
1 class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 int ans = 0;
4 for(int i=0; i < s.length(); i++) {
5 for(int j=i+1; j <=s.length(); j++) {
6 if(judge(s,i,j)) ans=Math.max(ans,j-i);
7 }
8 }
9 return ans;
10 }
11 public boolean judge(String s, int start, int end) {
12 Set<Character> set = new HashSet<Character>();
13 for(int i=start; i < end; i++) {
14 Character ch = s.charAt(i) ;
15 if(set.contains(ch)) return false;
16 set.add(ch);
17 }
18 return true;
19 }
20
21 }
wtf。。。还是TLE。。。嗯。。。。时间复杂度为O(n^3)。。惹不起惹不起
solution中提到滑动窗口这个抽象概念
确认过眼神，是在下太次了。。。
用滑动窗口的思想来解题：初始化两个索引 i, j，用HashSet来存储字符作为当前窗口。一开始，向右移动 j 的索引，如果索引指向的字符不在HashSet中，就继续向右移动直到碰到第一个在HashSet中的字符元素。此时，开始移动索引 i，用于遍历找到没有重复字符的窗口。当遍历完 i 或者 j 时，得到最终答案。
1 class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 Set<Character> set = new HashSet<Character>();//作为当前滑动窗口
4 int i=0, j=0, ans = 0;
5 int len = s.length();
6 while(i<len&&j<len){
7 if(!set.contains(s.charAt(j))){ //当前滑动窗口不包含索引为 j 的字符
8 set.add(s.charAt(j++)); //把字符加入当前滑动窗口，并更新索引 j
9 ans=Math.max(ans,j-i);//更新最大长度
10 } else {
11 set.remove(s.charAt(i++));//找到不包含与索引 j 指向的字符重复的滑动窗口
12 }
13 }
14 return ans;
15 }
16 }
此时的时间复杂度为O(n)。及时如此，我们可以发现，上述的代码还是存在一些不必要操作，比如"acvddf"，当 j=4的时候，i 开始遍历寻找不重复的滑动窗口，i 最终在等于4的时候停下，右轮到 j 开始。。。那么不必要的操作就是set.remove()，我们想如果可以得到当前窗口与 j 重复的字符下标就好了，i 可以直接从下标+1的位置开始。那么这样，set容器显然不能满足我们的需求，所以我们使用map接口来优化以上代码。
1 class Solution {
2 public int lengthOfLongestSubstring(String s) {
3 Map<Character,Integer> map = new HashMap<Character,Integer>();
4 int len = s.length();
5 int ans = 0;
6 for(int i=0,j=0; j<len; j++) {
7 if(map.containsKey(s.charAt(j))) {
8 i = Math.max(map.get(s.charAt(j)),i);
9 }
10 ans = Math.max(ans,j-i+1) ;
11 map.put(s.charAt(j),j+1) ;
12 }
13 return ans;
14 }
15 }
五、知识点补缺补漏
- public boolean add(E e)：向set集合增加一个元素，若该元素已经存在集合中，返回false表示增加失败，否则返回teue。
- public boolean remove(Object o)：如果指定元素存在，则从该集合中移除该元素，并返回true。
- public boolean contains(Object o)：如果该集合包含指定的元素，则返回true。
- public boolean containsKey(Object key)：如果此映射包含指定键的映射，则返回true。
- public V put(K key,V value)：将指定的值与此映射中的指定键关联。如果先前的映射包含键的映射，则替换旧值。