本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

1358. 包含所有三种字符的子字符串数目

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
示例 1：
输入：s = “abcabc”
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” 和 “abc” (相同字符串算多次)。
示例 2：
输入：s = “aaacb”
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 “aaacb”, “aacb” 和 “acb” 。
示例 3：
输入：s = “abc”
输出：1
提示：
3 <= s.length <= 5 x 10⁴
s 只包含字符 a，b 和 c 。

C++滑动窗口

n = s.lenght
性质一：如果s[i…j-1]是符合的子串，那么增大j后，s[i…j-1]也是符合的子串。
枚举i，计算每个i对应的最小j。最终结果是：$\sum$(n-j)
性质二：i1<i2，对应的j分别为j1,j2。则j1 <=j2。用反证法证明：令j1 > j2。
s[i2…j2]包括abc $\to$ s[i1…j2]包括abc $\to$ j2优于j1。
推论一：i++后，j不需要复位。即i,j都循环一轮，时间复杂度是：O(n)
注意：j为n是，nums[i…j-1]可能是，也可能不是。所以需要判断。

代码

核心代码

class Solution {
		public:
			int numberOfSubstrings(string s) {
				const int N = s.length();
				int cnt[3] = { 0 };
				int ans = 0;
				auto Is = [&]() {return cnt[0] && cnt[1] && cnt[2]; };
				for (int i = 0, j = 0; i < N; i++) {
					while ((j < N) && !Is()) {
						cnt[s[j] - 'a']++; j++;
					}
					if (Is()) { ans += N - j + 1; }
					cnt[s[i] - 'a']--;
				}
				return ans;
			}
		};

单元测试

string s;
		TEST_METHOD(TestMethod1)
		{
			s = "a";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "b";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s = "c";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod11)
		{
			s = "abcabc";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "aaacb";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "aaacb";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod14)
		{
			s = "abc";
			auto res = Solution().numberOfSubstrings(s);
			AssertEx(1, res);
		}