(5/30/16)Leetcode 3. Longest Sub

很久不刷题了，略有生疏，思路也不连贯。
总结：

1. 本题一开始想复杂了，目标应该focus到更新hashmap里面的值，一开始想法：不仅更新，且删除index在begin之前的所有hashmap的值。
   这种思路是对的，但是却没有必要，因为put本身就已经可以覆盖之前的值了。应该一切从简。HashMap中，put为主，remove少用。

2. 本题为Two Pointer与HashMap结合的题目: 本题返回的是长度，改为返回该substring也是可以的，只需加两个变量存储即可。fast pointer随着for循环移动, slow pointer在某种条件下激活并移动(这里的条件即为 map.containsKey(s.charAt(i))). 同一方向的Two pointer的题目大抵如此。(也有two pointer是从首位开始相对移动的)。

3. HashMap遍历的方法见：三种
   其中如果在遍历过程中需要删除entry，为了avoids a ConcurrentModificationException，需要用iterator而不能直接for遍历(本题初始思路要把slow pointer之前的entry删掉。。结果出现TLE)

4. 我的解法中需要记录的variable有slow, fast, max和curLength。既然记录了slow和fast就没有必要记录curLength了。对slow进行判断会更方便。

5. 合理使用Math.max代替if条件会让代码简洁好看。提高可读性

6. 改进过程:
   (1) naive version(with curLength, very silly):

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int maxLength = 0,curLength = 0;
        int slow = 0, pos = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++){
            //if not contains, just put into map
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), i);
                curLength ++;
            }
            else {
                pos = map.get(s.charAt(i));//get current position
                //if position is before slow pointer,just put and move slow pointer.
                if (pos < slow) {
                    map.put(s.charAt(i), i);
                    curLength ++;
                }
                else {
                    if (i - slow > maxLength) maxLength = i - slow;
                    curLength = i - pos; //not necessary
                    map.put(s.charAt(i),i);
                    slow = pos + 1;
                }
            }
        }
        return Math.max(maxLength, curLength);
    }
}

(2)删除掉curLength的版本：(looks better):

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int maxLength = 0;
        int slow = 0, pos = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++){
            //if not contains, just put into map
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), i);
            }
            else {
                pos = map.get(s.charAt(i));//get current position
                //if position is before slow pointer,just put and move slow pointer.
                if (pos < slow) {
                    map.put(s.charAt(i), i);
                }
                else {
                    if (i - slow > maxLength) maxLength = i - slow;
                    map.put(s.charAt(i),i);
                    slow = pos + 1;
                }
            }
        }
        return Math.max(maxLength, length - slow);
    }
}

(3)合并精简后版本(Final Version):(2)中的if else逻辑过多，代码是逐步修改精简的，好看的代码并不能一蹴而就。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int maxLength = 0;
        int slow = 0, pos = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++){
            if (map.containsKey(s.charAt(i))) {
                pos = map.get(s.charAt(i));
                if (pos >= slow) {
                    maxLength = Math.max(i - slow, maxLength);
                    slow = pos + 1;
                }
            }
            map.put(s.charAt(i), i);
        }
        return Math.max(maxLength, length - slow);
    }
}

(3)中merge了很多2中的逻辑，好看很多了！面试中不要着急一蹴而就，慢慢分析更改，思路清晰！