题目大意：
包含所有三种字符的子字符串数目
给你一个字符串 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^4s只包含字符 a，b 和 c 。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1358
解题思路分析：
看到这种求子串的问题，我们应该下意识想到使用双指针来解题。我们定义左右两个指针来代表当前子串区间范围。另外定义一个数组来记录每种字符在区间内的个数。开始时，左右指针均为0，我们先循环右指针（扩大区间范围），当左右指针范围内三种字符的个数都大于0时，当前区间内子串即是一个符合要求的答案，另外，因为当前区间为合理区间，那么当前左指针，与右指针到字符串尾部组成的所有子串都应该是合理区间，因此此时找到的合理子串数应该是字符串长度减去右指针。此时开始移动左指针，每移动一步（缩小区间范围），如果区间内字符个数仍然符合要求，继续添加符合条件的区间个数（字符串长度减去右指针）到返回结果，直到区间内三种字符中某个字符个数为0为止，这时返回继续移动右指针，重复上述步骤直到遍历完整个字符串。
实现代码：
public int numberOfSubstrings(String s) {
// 记录区间内a，b，c三中字符个数
int[] count = new int[3];
// 左右指针
int left=0,right=0;
// 返回结果
int res=0;
// 为了提高效率，将字符串转为数组
char[] arr = s.toCharArray();
// 循环
while(right<arr.length&&left<arr.length){
// 将右指针指向的字符个数加一
count[arr[right]-'a']++;
// 如果当前区间内三种字符个数均大于0
while(count[0]>0&&count[1]>0&&count[2]>0){
// 添加合理区间个数到返回结果
res+=(s.length()-right);
// 左指针指向字符个数减一
count[arr[left]-'a']--;
// 左指针向右移动一格
left++;
}
// 右指针向右移动一格
right++;
}
return res;
} 本题解法执行时间为7ms。
Runtime: 7 ms, faster than 83.49% of Java online submissions for Number of Substrings Containing All Three Characters.
Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Number of Substrings Containing All Three Characters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1358-number-of-substrings-containing-all-three-characters-解题思路分析/