滑动窗口算法是一种常用的解决字符串、数组相关问题的算法,其基本思想是通过维护一个窗口,来对问题进行处理。下面是滑动窗口算法的基本步骤:
定义两个指针 left 和 right,分别表示滑动窗口的左边界和右边界。
移动右指针 right,将窗口扩大,直到找到符合条件的解。
移动左指针 left,缩小窗口,直到不再符合条件。
重复步骤 2 和 3,直到遍历完整个数组或字符串。
具体步骤可能会根据具体题目而有所不同,但以上几点是滑动窗口算法的基本流程。
以下是一个示例题目及其解答:
给定一个字符串 s 和一个非空字符串 p,找出 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
示例 1:
输入: s = “cbaebabacd”, p = “abc” 输出: [0, 6] 解释: 起始索引为 0 的子串是 “cba”, 它是 “abc” 的字母异位词。 起始索引为 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
解答:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if not s or len(s) < len(p):
return []
p_count = [0] * 26
s_count = [0] * 26
for ch in p:
p_count[ord(ch) - ord('a')] += 1
res = []
for i in range(len(s)):
s_count[ord(s[i]) - ord('a')] += 1
if i >= len(p):
s_count[ord(s[i-len(p)]) - ord('a')] -= 1
if s_count == p_count:
res.append(i - len(p) + 1)
return res
时间复杂度: O(n),其中 n 为字符串 s 的长度。外层循环次数为 n,内层循环次数为常数,因此总时间复杂度为 O(n)。
空间复杂度: O(1)。由于字母表的大小是固定的,因此空间复杂度为常数。