自己的写法
//自己的做法:偏暴力解法,每次只挪动一下左指针或者右指针,在挪动右指针的时候记录下当前最大值
public static int lengthOfLongestSubstring(String s) {
if (s.length() < 2)
return s.length();
int left = 0, right = 1;
int res = 0;
while (right <= s.length()) {
if (isNoRepeat(s.substring(left, right))) {
res = Math.max(res, (right - left));
right++;
} else {
left++;
}
}
return res;
}
private static boolean isNoRepeat(String str) {
HashSet<Character> hashSet = new HashSet<>();
for (char c : str.toCharArray()) {
if (hashSet.contains(c)) {
return false;
}
hashSet.add(c);
}
return true;
}
官方的做法
//官方解法:滑动窗口思想,右指针移动到不能再移动,移动左指针,释放左窗口
public int lengthOfLongestSubstring1(String s) {
HashSet<Character> hashSet = new HashSet<>();
int n = s.length();
//右指针,初始值为-1,相当于在我们的字符串左边,还没有开始移动
int rk = -1, res = 0;
for (int i = 0; i < n; i++) {
if (i != 0) {
hashSet.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !hashSet.contains(s.charAt(rk + 1))) {
hashSet.add(s.charAt(rk + 1));
rk++;
}
//i ~ rk 是一个无重复子串
res = Math.max(res, rk - i + 1);
}
return res;
}
滑动窗口的应用场景
输入是线性的数据结构,如链表、字符串、数组,要求查找最长/最短子串、子数组、链表中的值;
可处理以下问题
1、大小为k的子数组最大和
2、带有k个不同字符的最长字串
3、寻找字符相同但排序不一样的字符串
双指针滑动窗口解法
右指针右移,移到不能移动为止;
然后左指针左移,释放窗口左边界;