Longest Substring Without Repeating Characters

该题lintcode可以过，leetcode超时过不了。 如何改进过leetcode呢？谢谢

1. public class Solution {
   
2.     public int lengthOfLongestSubstring(String s) {
   
3.         if(s == null || s.length() == 0)
   
4.         {
   
5.             return 0;
   
6.         }
   
7.         int result = 0;
   
8.         HashMap<Character, Integer> map = new HashMap<Character, Integer>();
   
9.         for(int i = 0; i < s.length(); i++)
   
10.         {
    
11.             if(!map.containsKey(s.charAt(i)))
    
12.             {
    
13.                 map.put(s.charAt(i), i);
    
14.             }
    
15.             else
    
16.             {
    
17.                 result = Math.max(result, map.size());
    
18.                 i = map.get(s.charAt(i));
    
19.                 map.clear();
    
20.             }
    
21.         }
    
22.         return Math.max(result, map.size());
    
23.     }
    
24. }

复制代码

你的程序的执行是，比如abcdefgd, 当遍历到第二个d时，你判断又重复了，然后比较了一个最大值，然后去HashMap里把第一个d的位置拿出来作为新的起始点，再重新遍历。所以你的efgd,相当于又遍历了一次，所以会超时。为何不维护一个类似sliding window的左右left, right边界，然后一边遍历，一边更新left, right, 然后计算之间的距离长度，在比较一个更长的结果呢？