【LeetCode 1358】Number of Substrings Containing All Three Characters【Medium】【JAVA】

女爷i 2021-09-21 03:18 295阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

题目几个关键信息：

*  该字符串只包含’a’，‘b’，'c’三种字符
 *  示例1中发现对于相同但是位置不同的子串，是按两个结果计算，无需去掉重复
 *  该字符串长度默认大于3

## 3. 方法 ##

### 3.1 思路 ###

最简单的思路就是暴力法，直接两个循环，并判断结果字符串是否都包含了’a’，‘b’，'c’三种字符。但该方法时间复杂度较高，O(n²)，因此考虑有没有简单的做法。  
题目是求符合条件的子串，这种要求很容易想到`双指针`进行遍历。

### 3.2 代码 ###

public int numberOfSubstrings(String s) { 
            int start = 0, end = 0, number = 0;
            int[] nums = new int[3];
    
            while (end < s.length()) { 
            	// 向后遍历，并标记出现的字符
                nums[s.charAt(end++) - 'a']++;
                // 当三个字符都包含时，移动start指针
                while (nums[0] > 0 && nums[1] > 0 && nums[2] > 0) { 
                	// 将start指针向后移动，直到再次无法同时包含三个字符
                	// 这时，start的值也为以end下标为字符串末位的，符合条件的子字符串数
                    nums[s.charAt(start++) - 'a']--;
                }
                number += start;
            }
    
            return number;
        }

### 3.3 运行结果 ###

![在这里插入图片描述][20200223105041347.png]

## 4. 相关链接 ##

[本题代码的github链接][github]  
[其他 Top 100 Liked Questions 题目][Top 100 Liked Questions]  
[其他 LeetCode 题目][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/cbadf21894604007950413cc7511dcac.png
[20200223105041347.png]: /images/20210920/ab0130df06bd46659f690f22f841284c.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page14/N1358_NumberOfSubstringsContainingAllThreeCharacters.java
[Top 100 Liked Questions]: https://blog.csdn.net/applying/article/category/9466044
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html