滑动窗口与双指针

字数

330 字

阅读时间

2 分钟

滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）

定长滑动窗口

定长滑动窗口问题的解决基本思想是三步

1. 构建定长窗口
2. 滑动窗口，对比出窗口和入窗口的元素
3. 根据变化更新状态

1456 定长子串中元音的最大数目

思路版：

impl Solution {
	pub fn max_vowels(s: String, k: i32) ->i32 {
		// 格式处理
		let s = s.as_byte();
		let k = k.as_usize();
		// 变量定义
		let mut ans = 0;
		let mut vowel = 0;
		
		for (i, &c) in s.iter().enumerate() { // 枚举窗口右端点
			// 1. 窗口构建
			if matches!(c, b'a' | b'e' | b'i' | b'o' | b'u') {
				vowel += 1;
			}
			if i + 1 < k {
				continue;
			}
			
			// 2. 更新
			ans = ans.max(vowel);
			if ans == k {  // 符合要求的字符数到达子串长度直接退出
				break;
			}
			
			// 3. 出窗口
			let out = s[i + 1 - k];
			if matches!(out, b'a' | b'e' | b'i' | b'o' | b'u'){
				vowel -= 1;
			}
		}
		ans as _
	}
}

技法版：

impl Solution {
	pub fn max_vowels(s: String, k: i32) ->i32 {
		const fn is_vowel(c: &u8) -> bool{
			matches!(c, b'a' | b'e' | b'i' | b'o' | b'u');
		}
		
		let init = s.as_byte().iter().take(k as usize).filter(|c| is_vowel(*c)).count() as i32;
		s.as_byte().iter().zip(s.as_byte().iter().skip(k as usize))
		.fold((init, init), |(count, max_count), (ready_out, ready_in)|
            match (is_vowel(ready_out), is_vowel(ready_in)) {
                (true, false) => (count - 1, max_count),
                (false, true) => (count + 1, max_count.max(count + 1)),
                _ => (count, max_count),
            }
        )
        .1
	}
}

贡献者

Kiracoon

页面历史

最后编辑于 2 个月前

查看完整历史

05286e7-LeetCode - 1456