学步园

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating
letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路

1 一开始还是要理解题目的意思。我一开始以为统计字符串中所有不相同的字符。ok，那么一个hashmap就能够解决问题。

2 输出wrong后，重新理解了题目。第一个想到的是暴力破解，把每个字串都检查，是否有重复的，然后找到没有重复的最大字串。需要时间O(n^3)

3 重新思考，自己随便写了字符串，自己会怎么找。wlrbbmqmqbhc 从头开始，看到之前没重复的字符就继续，碰到有重复的，就记下之前这个字符串的长度。然后从重复的一样的那个字符后一位重新开始找。这样一来，就把代码的基本逻辑给说清楚了。

4 上面的代码在最下面，空间上用hashmap来记录每次新查找字符串是否出现过，没有出现，就记录字符和相应的下标。如果出现过，把下标+1设为新的开始。这样的算法，最好情况O(n),最差情况O(n2),平均来看也不是线性的。

5 观察到，其实两个重复字符之间我们会重复检查，所以想办法缩减这部分。这样每次，碰到重复的字符，我们不要回去，而是知道在这之前没有重复的字符串长度为多少，继续检查。另外，可以用一个数组代替hashmap。虽然固定256，但是查找起来更加方便。

http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/

代码

public class Solution {
   public int lengthOfLongestSubstring(String s) {
		        if(s.length()==0){
		            return 0;
		        }
		        int n = s.length();
		        HashMap<Character,Integer> record = new HashMap<Character,Integer>();
		        int max=0;
		        int start =0;
		        while(start+max<n){
		            int cur = start;
		            while(cur<n&&!record.containsKey(s.charAt(cur))){
		                record.put(s.charAt(cur),cur);
		                cur++;
		            }
		            int tempmax = record.size();
		            if(tempmax>max){
		                max= tempmax;
		            }
		            if(cur==n){
		                max=record.size();
		                break;
		            }
		            start = record.get(s.charAt(cur))+1;
		            record.clear();
		        }
		        
		        return max;
		    }
}