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
- Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
- Set java類(lèi)型 TreeSet HashSet
暴力法
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j <= s.length(); j++) {
if (isUnique(s, i, j)) {
ans = Math.max(j - i, ans);
}
}
}
return ans;
}
public boolean isUnique(String s, int i, int j) {
Set<Character> chSets = new HashSet<>();
for (int z = i; z < j; z++) {
Character ch = s.charAt(z);
if (chSets.contains(ch)) return false;
chSets.add(ch);
}
return true;
}
}
時(shí)間復(fù)雜度O(n3)
劃窗口法
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0;
int n = s.length();
int ans = 0;
Set<Character> chSets = new HashSet<>();
while (i < n && j < n) {
if (!chSets.contains(s.charAt(j))) {
chSets.add(s.charAt(j++));
ans = Math.max(j-i, ans);
}
else {
chSets.remove(s.charAt(i++));
}
}
return ans;
}
時(shí)間復(fù)雜度： O（2n）
空間復(fù)雜度： O（min(m, n)）
opt sliding
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
Map<Character, Integer> chMaps = new HashMap<>();
for (int i = 0, j = 0; j < n; j++) {
if (chMaps.containsKey(s.charAt(j))) {
i = Math.max(i, chMaps.get(s.charAt(j)));
}
ans = Math.max(ans, j - i + 1);
chMaps.put(s.charAt(j), j + 1);
}
return ans;
}
滑窗口時(shí) i 也會(huì)遍歷n丸升， 遇到想重復(fù)的char ， i 直接跳到 臨近重復(fù)的下一個(gè)牺氨，避免遍歷狡耻。
