滑动窗口技术实现困惑：寻找指定长度连续递增子串

问题明确 #

给定字符串k和整数N，需要找出所有长度为N的连续子串，满足子串内字母严格连续递增（即每个后一个字符的ASCII码比前一个大1，比如cde、xyz这类序列）。

实现思路 #

1. 核心逻辑：固定窗口+递增校验优化 #

这个场景属于固定大小的滑动窗口，但可以通过维护连续递增长度来避免重复校验，大幅提升效率：

• 跟踪当前位置之前的连续递增字符长度：遍历字符串时，从第二个字符开始，判断当前字符是否比前一个字符的ASCII码大1。
  • 如果是，说明连续递增序列可延续，将当前连续长度加1；
  • 如果不是，说明序列中断，重置当前连续长度为1。
• 当连续递增长度达到或超过N时，说明存在符合条件的子串：子串起始位置为当前索引 - N + 1，结束位置为当前索引，直接截取该子串加入结果列表。

2. 分步拆解（以示例输入k='cdegoxyzcga'、N=3为例） #

• 初始化：current_length = 1（单个字符自身长度为1），结果列表result = []。
• 遍历索引i=1（字符d）：ord('d') = ord('c')+1，current_length变为2，小于3，不加入结果。
• 遍历索引i=2（字符e）：ord('e') = ord('d')+1，current_length变为3，等于N，截取子串k[0:3] = 'cde'加入result。
• 遍历索引i=3（字符g）：ord('g') != ord('e')+1，current_length重置为1。
• 遍历索引i=7（字符z）：ord('z') = ord('y')+1，current_length变为3，截取子串k[5:8] = 'xyz'加入result。
• 后续字符无法满足连续递增长度达3，最终结果为['cde', 'xyz']。

3. Python代码实现 #

def find_increasing_substrings(k, N):
    if N == 1:
        return list(k)
    result = []
    current_length = 1
    for i in range(1, len(k)):
        if ord(k[i]) == ord(k[i-1]) + 1:
            current_length += 1
        else:
            current_length = 1
        # 连续长度达标时，截取对应子串
        if current_length >= N:
            substring = k[i - N + 1 : i + 1]
            result.append(substring)
    return result

# 测试示例
k = 'cdegoxyzcga'
N = 3
print(find_increasing_substrings(k, N))  # 输出: ['cde', 'xyz']

对比传统固定窗口思路 #

朴素固定窗口方式需每次滑动后遍历窗口内所有相邻字符校验，时间复杂度为O(M*N)（M为字符串长度）；上述优化方式仅需一次遍历，时间复杂度为O(M)，效率提升明显。

内容的提问来源于stack exchange，提问作者DSNWU