從昨天開始，我想每天寫一道算法題，雖然比較簡單，但是相信積累起來還是有借鑒意義的。所以想用博客的方式記錄下來。
題目
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring , "pwke" is a subsequence and not a substring.
分析 給定一個字符串，求出該字符串的最長字串的長度。
要求： 字串不能包含重復字母 是字串，而不是子序列測試數(shù)據(jù) 輸入：abcabcbb 輸出：3 輸入：aab 輸出：2
參考答案 這個題的解法有很多，這里只給出我自己的代碼和我認為比較好的代碼。
自己的答案： 算法思想： 從左到右遍歷給定的字符串，用subString臨時保存字串。 每加入一個新的字母，檢查subString是否包含該字母， 如果有，那么從subString中那個字母的下標+1開始，構造新的字串。 如果沒有包含，那么subString末尾加上新字母，并且記錄下最大值。public int lengthOfLongestSubstring(String s) { String subString = ""; String temp;//用與保存字母 int max = 0;//最大長度 for(int i =0;i<s.length();i++){ temp = s.charAt(i)+""; if(subString.contains(temp)){ //包含temp字母 如：abc temp=b //那么index = 1 且subString = cb int index = subString.indexOf(temp); subString = subString.substring(index+1) + temp; }else{ //沒有包含 構造新的字符串 subString += temp; max=Math.max(subString.length(),max); } } return max; }更好的答案 采用哈希表來存儲字串的字母，查看新字母是否有重復更快捷。public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; }}時間復雜度：O(n) 空間復雜度：O(min(m,n))
巧妙的方法 利用ASCII碼值public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; int[] index = new int[128]; // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { i = Math.max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] = j + 1; } return ans; }}時間復雜度：O(n) 空間復雜度：O(m)
新聞熱點
疑難解答
