算法一:暴力
暴力找出所有的子串时间复杂度为$O(n^2)$,对于每个子串遍历一遍查看有无重复元素时间复杂度为$O(n)$,所以总的时间复杂度为$O(n^3)$,会超时,所以想一下如何做优化。
算法二:滑动窗口
将左右指针初始化成0,左指针每次向右移动1,右指针一直向右移动直到碰到重复的元素,这样一定能找到答案,因为这样是按照子串的开头遍历的,所以一定包含所有的情况。时间复杂度:因为i和j分别最多移动n次,所以为$O(2n)$
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> hash = new HashSet<>();
int ans = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
if (i > 0) {
hash.remove(s.charAt(i - 1)); // 因为i向右移动1,那么i-1位置上的字符从hash中删除
}
while (j < s.length() && !hash.contains(s.charAt(j))) { // 只要j不超过长度并且无重复元素则一直向右移动
hash.add(s.charAt(j)); // 将该字符加到hash中
j++;
}
ans = Math.max(ans, j - i); // 这里要注意的是不是j-i+1因为j停止时是包含重复元素的所以要再减去1
}
return ans;
}
}
以右指针遍历,参考yxc
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int ans = 0;
for (int j = 0, i = 0; j < s.length(); j++) {
if (map.containsKey(s.charAt(j))) {
int k = i;
i = map.get(s.charAt(j)) + 1;
for (int u = k; u < i; u++) {
map.remove(s.charAt(u));
}
}
map.put(s.charAt(j), j);
ans = Math.max(ans, j - i + 1);
}
return ans;
}
}