一、題目描述
給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
二、思路
（1）暴力解法
頭指標指向頭元素，尾指標從頭元素開始，每遍歷一個元素，就把該元素放入set中，并更新最大長度，當遇到重復的元素時，同樣更新最大長度，并將頭指標往后順延一個，接著清空set，開始下一輪，
代碼實作：
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
Set<Character> set = new HashSet<>();
int max = 0;
for (int i = 0; i < s.length(); i++) {
set.clear();
char start = s.charAt(i);
set.add(start);
for (int j = i + 1; j < s.length(); j++) {
char temp = s.charAt(j);
if (!set.contains(temp)) {
set.add(temp);
max = Math.max(max, set.size());
} else {
max = Math.max(max, set.size());
break;
}
}
}
return max;
}時間復雜度為O(n2)，空間復雜度為O(n)，
提交答案：
（2）滑動視窗
設定一個start指標，指向子串首元素，再設定一個end指標，指向當前的子串尾元素，
一開始start=0，end=start，接著end自增，并將遍歷過的字符作為key，其下標作為value，存入map中，一旦end指向的元素num發生重復，并且滿足上一次出現的num元素的下標+1>start時（有可能上一次出現的num元素的下標+1小于start時，防止star倒退），使得start=上一次出現的num元素的下標+1，
代碼實作：
public int lengthOfLongestSubstring(String s) {
int max = 0;
int length = s.length();
Map<Character, Integer> map = new HashMap<>();
for (int start = 0, end = 0; end < length; end++) {
char endChar = s.charAt(end);
if (map.containsKey(endChar) && (map.get(endChar) + 1) > start) {
start = map.get(endChar) + 1;
}
max = Math.max(max, end - start + 1);
map.put(s.charAt(end), end);
}
return max;
}時間復雜度為O(n)，空間復雜度也為O(n)，
提交答案：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145438.html
標籤：其他