LeetCode：無重復字符的最長子串
利用滑動視窗獲得字串無重復最長子串
No.3 無重復字符的最長子串
題目：
給定一個字串，請你找出其中不含有重復字符的最長子串的長度
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1
示例 3：
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串
解法：
-
滑動視窗
時間復雜度：\(O(n)\)
空間復雜度：\(O(min(m,n))\)
滑動索引控制 [ i，j ）區間，用 Set 判斷重復
public int lengthOfLongestSubstring(String s) { int len = s.length(); int i = 0, j = 0, sum = 0; Set set = new HashSet(); while (i < len && j < len) { if (set.add(s.charAt(j))) { j++; sum = Math.max(sum, j - i); } else { set.remove(s.charAt(i++)); } } return sum; } -
窮舉所有組合
時間復雜度：\(O(n^2)\)
空間復雜度：\(O(min(m,n)\)
以每一位為起始點，從起始點向后判斷，用 Set 判斷重復
public int lengthOfLongestSubstring(String s) { int length = s.length(); HashSet set = new HashSet(); char[] chars = s.toCharArray(); int sum = 0; if (length == 1) { return 1; } for (int i = 0; i < length - 1; i++) { set.add(chars[i]); for (int j = i + 1; j < length; j++) { if (set.contains(chars[j])) { break; } else { set.add(chars[j]); } } sum = Math.max(set.size(), sum); set.clear(); } return sum; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/159504.html
標籤：其他
下一篇：LeetCode：最長回文字串