hot100之滑动窗口
无重复字符的最长字串(003)先看代码
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
int lef = 0;
int rig = 0;
int[] memo = new int;
while (rig < s.length()){
char clef = s.charAt(lef);
char crig = s.charAt(rig);
if (memo > 0){
memo--;
lef++;
continue;
}
memo++;
res = Math.max(res, rig - lef + 1);
rig++;
}
return res;
}
}
[*]分析
根据题目条件
通过lef和rig 维护一个滑动窗口, memo来记录遇到字符的次数
rig一直向右扩张, 当出现数字重复, 移动lef 收缩窗口
[*]感悟
寻找连续区间就让人很自然而然想到滑动窗口
每次窗口移动只用考虑(入窗口, 出窗口)的元素对窗口整体的影响
找到字符串中所有的字母异位词(438)
先看代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int lef = 0;
int rig = 0;
int[] memo = new int;
for (char c : p.toCharArray()){
memo++;
}
while(rig < s.length()){
int idx = s.charAt(rig) - 'a';
memo--;
while(memo < 0){
memo++;
lef++;
}
if (rig - lef + 1 == p.length()) res.add(lef);
rig++;
}
return res;
}
}
[*]分析
和无重复字符的最长字串基本一致, 扩张收缩窗口, 达到条件添加到res
[*]感悟
暂无
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]