Leetcode Two Sum (java)Longest Substring Without Repeating Characters

解法一：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        if (s.length() <= 1) {
            max = s.length();
            return max;
        }
        for (int i = 0; i < s.length(); i++) {
            //新建一個StringBuilder存儲臨時字元串
            StringBuilder str = new StringBuilder();
            str.append(String.valueOf(s.charAt(i)));
            //判斷每個字元串多長
            for (int j = i + 1; j < s.length(); j++) {
                //當出現相同字元串則停止匹配跳出
                if (str.indexOf(String.valueOf(s.charAt(j))) == -1) {
                    str.append(String.valueOf(s.charAt(j)));
                }
                else{
                    break;
                }
            }
            //記錄最大長度
            if (str.length() > max) {
                max = str.length();
            }
        }
        return max;
    }
}

　這種解法使用的是Brute Force演算法，即是暴力搜索匹配，時間複雜度較高

解法二：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        //存儲每個字元出現的位置
        Hashtable<Character, Integer> map = new Hashtable<Character, Integer>();
        //遍歷字元串
        for (int i = 0, j = 0; i < s.length(); i++) {
            //當出現相同字元時改變視窗左邊框位置並記錄視窗長度
            if (map.containsKey(s.charAt(i))) {
                j = Math.max(map.get(s.charAt(i)) + 1 , j);
            }
            max = Math.max(max, i - j + 1);
            map.put(s.charAt(i), i);
        }
        return max;
    }
}

　這種解法的思想是計算兩個相同的字元之間的長度，好比作一個視窗在字元串上右邊框向右拉伸，若右邊框碰到視窗內已存在的字元，那麼左邊框向右拉伸到到視窗已存在字元的右邊，時間複雜度較低

github地址：https://github.com/CyanChan/leetcode