1876. 长度为三且各字符不同的子字符串

对读者的要求

• 了解for, while两种循环结构；

• 或许在游戏中拿过三杀；

• 能够计算简单组合数；

题意简述

找出长度为3的连续字符串的个数；

字符串长度的值域 [1, 100]。

方法一：双指针

从头开始遍历，取连续的三个字符，统计个数；

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N)。此处的 n 指的是字符串 s 的长度，实际上只会运行 n - 3 次。

• 空间复杂度：O(1)。使用一个长度为3的哈希表，作为一个滑动数组空间，将会使用 n - 3次。

备注

• 两次debug： 没有阅读题目下面的限制条件，s 的长度可以为1，而支撑判断需要至少三个字符，因此需要特判；

• 主串无需遍历全串，连续串从0位序开始，最多遍历到 n - 3；

方法二：遍历 + 判断

遍历连续字符串，判断他们三个数组成的长度为2，数量为3的数对，是否每个数对都不相等；

Python版本

C++版本

复杂度分析

• 时间复杂度： O(n)。此处的长度n 指的是 字符串s长度为n。 但仅需要遍历到 n - 2的位置

• 空间复杂度： O(1)。

备注

• 对于 C++ 而言，如果在for循环中将s.length()的值作为上限，可能导致堆栈溢出；

• 导致堆栈溢出的原因是 unsigned int可能由负数直接转换为较大正数，从而导致程序出错，测试代码如下：

• 因此先使用一个变量【确定的数据类型】，保存s.length()的值，然后再放入循环中进行遍历,虽未找到原因，但官解中经常遇到这样的写法；