滑动窗口相关问题总结
2023-12-14 21:49:48
滑动窗口题目总结
滑动窗口的大小可以改变
- 定义需要维护的变量
- 定义窗口首尾端及其它变量
- 窗口开始滑动
- 考虑把index=right位置的元素纳入窗口后 窗口是否仍然满足要求
-
- 不是 left不断右移 直到把index=right位置的元素纳入窗口后 窗口仍满足要求;left右移的过程中更新需要维护的变量【剪枝位置2 考虑是否能快速定位到新left的位置 不需要left一步一步右移】
-
- 是 则继续往下
- 把index=right位置的元素纳入窗口
- 更新需要维护的变量
- 窗口滑动结束 返回结果
3. 无重复字符的最长子串
- 找到满足特定条件的子串
- 使用HashMap可以快速锁定重复元素上次出现的位置,便于动态的调整left指针的位置。
- 保证窗口中的元素都不重复即可。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 不使用数组是因为不好确定数组的大小。同时无法记录字符上一次出现的位置
HashMap<Character, Integer> map = new HashMap<>();
int res = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
char ch = s.charAt(right);
// 这就是HashSet做不到的功能,没法查找该元素上一次出现的位置。
if(map.containsKey(ch)) left = Math.max(left, map.get(ch)+1);
// 可以更新ch所在的位置。
map.put(ch,right);
res = Math.max(res, right-left+1);
}
return res;
}
}
文章来源:https://blog.csdn.net/weixin_46367158/article/details/135003984
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!