题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，由 a b c 组成，找出其中所有至少包含a b c各一个的子字符串。

思路分享

  • 不定长滑动窗口变式，变在“至少”，也就是说，一旦找到一个合适的窗口，就是一个合适的窗口右端点，窗口左侧一直往左都是答案，所以最终计算答案时，直接看包含 a b c 至少各一个的最短窗口的左端数值之和。

  • 不过具体判断窗口是否满足条件，除了直接计算对三个字母的记录是否都非零外，也可以引入另一个变量统计当前字母为零的个数，看起来更快，但实际上差别不大，复杂度都是O(1)。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int numberOfSubstrings(string s) {
        int rec[3]{};
        int left = 0;
        int ans = 0;
        int n = s.size();
        int empty = 3;
        for (int right = 0; right < n; right++) {
            int index = s[right]-'a';
            if (rec[index]++ == 0) empty--;
            while (empty == 0) {
                if (--rec[s[left++]-'a']==0) {
                    //cout << left-1 << " " << right << endl;
                    ans += left;
                    empty++;
                }
            }
        }
        return ans;
    }
};class Solution {
public:
    int numberOfSubstrings(string s) {
        int rec[3]{};
        int left = 0;
        int ans = 0;
        int n = s.size();
        int empty = 3;
        for (int right = 0; right < n; right++) {
            int index = s[right]-'a';
            if (rec[index]++ == 0) empty--;
            while (empty == 0) {
                if (--rec[s[left++]-'a']==0) {
                    //cout << left-1 << " " << right << endl;
                    empty++;
                }
            }
            ans += left;
        }
        return ans;
    }
};
/*class Solution {
public:
    int numberOfSubstrings(string s) {
        int rec[3]{};
        int left = 0;
        int ans = 0;
        int n = s.size();
        for (int right = 0; right < n; right++) {
            rec[s[right]-'a']++;
            while (rec[0]&&rec[1]&&rec[2]) {
                //cout << left << " " << right << endl;
                rec[s[left++]-'a']--;
            }
            ans += left;
        }
        return ans;
    }
};*/