[数据结构与算法]3. 无重复字符的最长子串

1. class Solution {
2.    public int lengthOfLongestSubstring(String s) {
3.     int left = 0;
4.     int result = 0;
5.     HashMap<Character,Integer> hashMap = new HashMap<Character,Integer> ();
6.     for(int i=0; i<s.length(); i++){
7.         if(hashMap.containsKey(s.charAt(i))) {
8.            left = Math.max(left, hashMap.get(s.charAt(i))+1);
9.          }
10.         hashMap.put(s.charAt(i),i);
11.         result = Math.max(result, i-left+1);
12.     }
13.     return result;
14.   }
15.  }

执行用时：4 ms, 在所有?Java?提交中击败了87.65%的用户

内存消耗：38.6 MB, 在所有?Java?提交中击败了36.23%的用户

解析如下：

????????第六行代码，遍历整个S字符串， 如果在hashmap里面找到了包含前面的某一个字符，便将左指针往右移一个单位。

? ? ? ? 但是会存在这种情况，假设字符串是abba， 现在左指针left已经指向第二个b，然后执行第七行代码，发现条件成立，而此时hashMap.get（a）其实获取的是字符串abba里面的第一个a ，它的值为hashMap.get(a) = 0,? 很明显不是我们所期望的第二个a， 所以在这里要将左指针和hashmap.get()的值作比较，取最大的值。

? ? ? ? 然后在result里面，比较之前的字符串长度和现在的字符串长度哪一个长，返回最大值即可。