计数类问题
# 计数类问题
计数类问题一般是指求符合题意条件下的个数问题，比如子串个数、子数组个数等。这里问题是滑动窗口的特殊类型，在滑动窗口这个框架下，利用窗口的滑动去不断累加计算个数。
双指针算法是在左边界固定的前提下，让右边界走到最右边，所以滑动窗口一般用于极值类问题，比如最大、最小等。计数类问题有些会让求解满足特定区间范围或者恰好等于等准确性问题，这里问题一般需要转化。比如
- 满足特定区间范围，比如求整数数组最大元素满足[min, max]的子数组个数，转化为：最大元素小于等于max的子数组个数 - 最大元素小于等于 min-1 的子数组个数
- 恰好等于，比如求整数数组中恰好等于k个不同元素的连续子区间个数，转化为：最大k个不同元素的子区间个数 - 最大k-1个不同元素的子区间个数
这类问题还需要知道一个知识点，求解区间满足条件的连续子区间个数方法：不断累加新连续区间元素个数
- 区间元素个数值计算方法，对于[left, right]区间，元素个数为 right - left + 1
注意，计算连续子区间数值的方法和计算连续子串的方法相同。
// 求解满足条件的连续子区间个数
let left = 0;
let right = 0;
let count = 0;
while(right < n){
// 满足条件下,累加 count
count += right - left + 1;
right++;
}
// 举个例子
{
Q：求[0,1,2]的连续子区间个数
A：
1. 区间 [0,0] ，个数：1， 子区间为：[0]
2. 区间 [0,1] ，个数：right - left + 1 = 1 - 0 + 1 = 2，新增子区间为：[0, 1], [1]
3. 区间 [0,2] ，个数：right - left + 1 = 2 - 0 + 1 = 3，新增子区间为：[0, 1, 2], [1,2], [2]
所以，总个数为：1+2+3 = 6，子区间分别为：[0],[0, 1], [1],[0, 1, 2], [1,2], [2]
}
技术类问题滑动窗口的一个特定类型，可用不定长或定长模板解决，具体需要根据问题具体分析，因此这类问题没有图示和模板。
# 例题
# LC 713.乘积小于-k-的子数组
Q：给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
A：本题适合作为计数类的入门题目，核心注意点是需要知道计算连续子数组数量的方法
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numSubarrayProductLessThanK = function (nums, k) {
let left = 0;
let right = 0;
let ans = 0;
let product = 1; // 乘积，所以起始为1
while (right < nums.length) {
product *= nums[right];
// 边界case，k = 0，所以需要加上 left <= right，一般来说这类题目，加上此判断会比较保险
while (product >= k && left <= right) {
product /= nums[left];
left++;
}
// 计算连续子数组数量：不断累加新连续区间元素个数
ans += right - left + 1;
right++;
}
return ans;
};
# LC 795.区间子数组个数 (opens new window)
Q：给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
A：本题的核心在于转化，滑动窗口适合用来解决极值问题，所以当题目为求解某准确性问题时，需要对题目分析做出转化。本题可转化为：满足最大元素在 [left, right] 区间内的连续子区间元素个数 = 最大元素小于等于right的连续子数组个数 - 最大元素小于等于left-1连续子数组个数
/**
* @param {number[]} nums
* @param {number} left
* @param {number} right
* @return {number}
*/
var numSubarrayBoundedMax = function (nums, left, right) {
// 寻找 <= limit的连续子区间 个数
const findCount = (limit) => {
let l = 0;
let r = 0;
let ans = 0;
while (r < nums.length) {
if (nums[r] > limit) {
// 超过最大值后，则直接移动到最大值后开始寻找
l = r + 1;
} else {
// 累加连续子数组个数
ans += r - l + 1;
}
r++;
}
return ans;
}
// 满足子区间元素个数 = 最大元素小于等于right的连续子数组个数 - 最大元素小于等于left-1连续子数组个数
return findCount(right) - findCount(left - 1);
};
# LC 992.k-个不同整数的子数组 (opens new window)
Q：
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。 子数组 是数组的 连续 部分。
A：题目写的比较繁琐，其实就是求解包含k个不同整数的子数组个数，很多题目都是类似，饶了一堆概念，其实就是求解一个问题，需要对题目进行分析，抓住本质，从另一个方面也锻炼分析能力，快速抓住问题本质。本题的核心也是转化：求k个不同元素的子数组 = 最大为k个不同元素的子数组 - 最大为 k-1 个不同元素的子数组。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraysWithKDistinct = function (nums, k) {
// 求k个不同元素的子数组数量 = 最大为k个不同元素的子数组数量 - 最大为 k-1 个不同元素的子数组数量
// 使用Map作为滑动窗口数据结构
const findCount = (limit) => {
const window = new Map();
let left = 0;
let right = 0;
let ans = 0;
while (right < nums.length) {
window.set(
nums[right],
window.has(nums[right]) ? window.get(nums[right]) + 1 : 1
);
// 超过 limit 则需要收缩窗口
while (window.size > limit) {
const count = window.get(nums[left]) - 1;
if (count == 0) {
window.delete(nums[left]);
} else {
window.set(nums[left], count);
}
left++;
}
// 不断累加新连续区间元素个数
ans += right - left + 1;
right++;
}
return ans;
};
return findCount(k) - findCount(k - 1);
};
# LC 904.水果成篮 (opens new window)
Q：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
A：题目写的比较绕，分析后可得出本题其实是求一个数组中最大元素种类为2的最长区间。本题用哈希表的解法较为简单，用哈希表记录种类，超过就收缩窗口，求解出最长区间。核心理解数组解法，使用一个长度为2的数组去求解，效率较高。
/**
* @param {number[]} fruits
* @return {number}
*/
var totalFruit = function (fruits) {
/*
解法一，滑动窗口，哈希表
核心思路：
1. 题目转化为：求一个滑动窗口内，最大数字种类为2个最长区间
2. 基本解法，使用哈希表记录窗口水果种类，该解法为标准的滑动窗口解法
时间复杂度：O(n)
空间复杂度：O(n)
*/
{
// 求一个滑动窗口内，最大数字种类为2个最长区间
const window = new Map();
const k = 2;
let left = 0;
let right = 0;
let maxL = 0;
while (right < fruits.length) {
window.set(
fruits[right],
window.has(fruits[right]) ? window.get(fruits[right]) + 1 : 1
);
while (window.size > k) {
const count = window.get(fruits[left]) - 1;
if (count == 0) {
window.delete(fruits[left]);
} else {
window.set(fruits[left], count);
}
left++;
}
maxL = Math.max(maxL, right - left + 1);
right++;
}
return maxL;
}
/*
解法二，滑动窗口，数组，效率比哈希表高点
核心思路：
1. 题目转化为：求一个滑动窗口内，最大数字种类为2个最长区间
2. 基本解法，使用 数组 记录窗口水果种类
时间复杂度：O(n)
空间复杂度：O(n)
*/
{
let left = 0;
let right = 0;
let maxL = 0;
let next = 0; // 记录右指针遇到不同种类时的位置，该位置用于左指针移动，该变量为本解法的精华与难点
const kinds = [fruits[left]]; // 记录窗口内水果种类，最大为2个元素
while (right < fruits.length) {
if (!kinds.includes(fruits[right])) {
if (kinds.length <= 1) {
// 初始化时已经加入了一个种类，因此这里至少一个种类
kinds[1] = fruits[right];
} else {
// 移动左指针，因为next表示的是“右指针遇到不同种类时的位置”，这里遇到了新的不同种类，那么next就表示上个种类的位置，因此可以作为左指针的移动位置
left = next;
// 这里right遇到了不同种类，那么 right - 1 必定是另一个种类
kinds[0] = fruits[right - 1];
kinds[1] = fruits[right];
}
}
// next 记录右指针遇到不同种类时的位置，当 right 与 next不同时，就要更新 next
if (fruits[right] != fruits[next]) {
next = right;
}
maxL = Math.max(maxL, right - left + 1);
right++;
}
return maxL;
}
};
# LC 467.环绕字符串中唯一的子字符串 (opens new window)
Q：
把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串，所以 s 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." 。 现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量 。
A：题目还是比较绕，其实就是求解p的连续子串数量，其中"za"视为连续。通过本题需要掌握计算子串数量的一种方法：使用一个频数数组，统计以每个字符结尾的逻辑连续子串的最大长度，然后对频数数组相加即可求得答案。理解这一点很重要，比如 "abc"，那么freq["c"] = 3，即子字符串有三个: "abc", "bc", "c"，保证了每个子串的唯一，则 freq 会记录为: a: 1, b: 2, c: 3，则所有子串即为 1 + 2 + 3 = 6
/**
* @param {string} p
* @return {number}
*/
var findSubstringInWraproundString = function (p) {
/*
解法一，滑动窗口，计数类，数组
核心思路：
1. 怎么解决无线环绕？使用ASCII码差值, d=1 或 d = -25("za" 的情况)
2. 怎么保证子串不同？使用一个频数数组，统计以每个字符结尾的逻辑连续子串的最大长度，然后对频数数组相加即可求得答案。理解这一点很重要，比如 "abc"，那么freq["c"] = 3，即子字符串有三个: "abc", "bc", "c"，保证了每个子串的唯一，则 freq 会记录为: a: 1, b: 2, c: 3，则所有子串即为 1 + 2 + 3 = 6
注意点：
1. 本题的滑动窗口概念不是特别明显
2. 技术类问题一般用动态规划实现，滑动窗口解法是一种特殊形式
时间复杂度：O(n)，其中 n 是字符串 p 的长度。
空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，故 ∣Σ∣=26。
*/
{
// 求p的非空连续字母表子串数目，注：za连一起
const freq = new Array(26).fill(0); // 频数数组，统计以每个字符结尾的逻辑连续子串的最大长度
const aCode = "a".charCodeAt();
let count = 0;
p = "_" + p; // 哨兵字符，类似哨兵节点的概念，前面加一个字符串，方便 做 p[i] - p[i - 1] 统计，避免对开头的判断
for (let i = 1; i < p.length; i++) {
const d = p[i].charCodeAt() - p[i - 1].charCodeAt();
// 为连续子串的条件：d = 1 （例如 "ab"） 或 d = -25 ("za" 的情况)
if (d == 1 || d == -25) {
// 如果为连续子串，则 count 累加，即 count 表示 以当前字符结尾的逻辑连续子串的最大长度
count++;
} else {
// 非连续子串，则赋值为1
count = 1;
}
// 统计当前字符结尾的逻辑连续子串的最大长度
const index = p[i].charCodeAt() - aCode;
freq[index] = Math.max(count, freq[index]);
}
// 计算答案，之和即为最终答案
let ans = 0;
for (const val of freq) {
ans += val;
}
return ans;
}
};
# 小结
计数类问题是滑动窗口的一种特殊类型，这类问题也基本用动态规划。
这类问题归纳下有几个知识点：
- 求解区间满足条件的连续子区间个数方法：不断累加新连续区间元素个数
- 区间元素个数值计算方法，对于[left, right]区间，元素个数为 right - left + 1
- 这里问题一般需要转化，把准确性问题转化为极值类问题：
- 满足特定区间范围，比如求整数数组最大元素满足[min, max]的子数组个数，转化为：最大元素小于等于max的子数组个数 - 最大元素小于等于 min-1 的子数组个数
- 恰好等于，比如求整数数组中恰好等于k个不同元素的连续子区间个数，转化为：最大k个不同元素的子区间个数 - 最大k-1个不同元素的子区间个数
- 两个特殊解法
- 计算子串数量的一种方法：使用一个频数数组，统计以每个字符结尾的逻辑连续子串的最大长度，然后对频数数组相加即可求得答案。
- 水果成篮的数组解法中next指针的用法