难度: Medium
Submission
运行时间: 36 ms
内存: 16.2 MB
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if not s or len(s) < k:
return 0
left, right = 0, 0
count = 0
seen = {}
while right < len(s):
if len(seen) < k:
# 如果当前窗口的大小小于k，不断向右扩展窗口
if s[right] not in seen:
seen[s[right]] = right
right += 1
else:
# 如果遇到重复字符，左指针向右移动，并移除左指针位置的字符
del seen[s[left]]
left += 1
else:
# 如果当前窗口的大小等于k，说明找到了一个满足条件的子串
count += 1
# 左指针向右移动，并移除左指针位置的字符
del seen[s[left]]
left += 1
return count
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if not s or len(s) < k:
return 0
left, right = 0, 0
count = 0
seen = {}
while right < len(s):
# 如果当前字符没有出现过，则将其加入窗口
if s[right] not in seen:
seen[s[right]] = right
right += 1
# 当窗口大小达到k时，找到一个满足条件的子串
if len(seen) == k:
count += 1
# 移除窗口最左边的字符
del seen[s[left]]
left += 1
else:
# 如果当前字符已经出现过，则移动左指针直到移除重复字符的位置
while s[right] in seen:
del seen[s[left]]
left += 1
# 将当前字符加入窗口
seen[s[right]] = right
right += 1
# 当窗口大小达到k时，找到一个满足条件的子串
if len(seen) == k:
count += 1
return count
Explain
此题解采用了滑动窗口的方法来寻找长度为 K 且不包含重复字符的子串。定义两个指针 left 和 right 表示窗口的左右边界。使用一个字典 seen 来记录当前窗口中字符的最新位置。当窗口中的字符数达到 K 且没有重复时，此窗口为一个有效的子串。每次当窗口有效时，计数加一，并向右滑动窗口。如果遇到重复字符，则调整左指针直到该重复字符被排除出窗口。
时间复杂度: O(n)
空间复杂度: O(min(n, k))
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if not s or len(s) < k:
return 0
left, right = 0, 0
count = 0
seen = {}
while right < len(s):
if s[right] not in seen:
seen[s[right]] = right # 记录字符的位置
right += 1
if len(seen) == k: # 检查窗口大小是否为 k
count += 1 # 找到一个有效子串
del seen[s[left]] # 移除窗口最左边的字符
left += 1
else:
while s[right] in seen: # 处理窗口中的重复字符
del seen[s[left]]
left += 1
seen[s[right]] = right
right += 1
if len(seen) == k:
count += 1
return count
Explore
在滑动窗口算法中，目标是维持一个窗口内的字符不重复，以便快速判断当前窗口是否为符合条件的子串。如果遇到重复字符，通过移动左指针来排除重复，可以最大限度地保持窗口的大小和连续性，从而避免错过潜在的有效子串。如果直接跳过重复字符或重置窗口，将丢失当前窗口之前的所有有效信息，效率低下且可能错过其他有效的子串。
这种处理方式确实可能导致错过某些有效的长度为K的子串。当移除窗口最左边的字符后，窗口大小立即减小，接下来的字符可能与已移除的字符形成新的有效子串。然而，该题解的逻辑在每次窗口达到K时只记录一次子串并立即缩小窗口，没有考虑继续维持窗口大小为K来探索后续可能的子串。这可能需要更细致的窗口滑动处理来捕捉所有可能的子串。
选择删除左侧字符直到不再有重复的方法可以细致地控制窗口内的字符组成，确保每一步都尝试形成有效的子串。而直接将左指针移动到重复字符的下一个位置虽然简单，但可能跳过某些有效的子串的组合，因为这种跳跃式的移动会使窗口中间的其他字符组合未被充分考虑。逐个移除左侧字符的方法提供了更多的灵活性和可能性，以找到所有的有效子串。
题解中这样处理主要是为了简化操作和逻辑。每次窗口达到K时记录一次有效子串，然后通过移动左指针来探索新的可能性，这样可以避免复杂的窗口管理。虽然这种方法可能会错过一些子串，但总体上可以有效地找到大部分有效子串。要完全不错过任何可能的子串，可以采用更复杂的窗口调整策略，如在每个右指针移动后都检查从当前左指针开始的所有长度为K的窗口。