如何计算判断数组包含子数组所需的总比较次数？

核心公式 #

总比较次数 = 大数组元素个数 - 小数组元素个数 + 1

原理说明 #

要在大数组中寻找与小数组完全匹配的连续子数组，本质是统计大数组中所有能容纳小数组的起始位置数量：

• 设大数组长度为 n，小数组长度为 m
• 起始位置的范围从大数组的第1个元素（索引0）到第 n - m + 1 个元素（索引 n - m）
• 每个起始位置对应一次完整的匹配比较，因此总次数就是 n - m + 1

示例验证 #

对应你给出的代码示例：

largeArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
smallArr = [9, 10]

大数组长度 n=10，小数组长度 m=2，代入公式得：10 - 2 + 1 = 9，和你描述的第9次匹配成功的场景完全一致。

边界情况处理 #

如果小数组长度 m 大于大数组长度 n，公式计算结果会≤0，说明不可能存在匹配，直接跳过比较逻辑即可。

内容的提问来源于stack exchange，提问作者valdimar.ein