核心思路

一般是求子数组的问题。

双/三指针的计数问题一般是：对于每一个右边界，找到满足条件的左边界。对于不满足的条件的边界加上一个标志。对于满足条件的边界，需要加上一个标志。

例题

leetcode 2444. 统计定界子数组的数目

题解

• 代码

class Solution {public long countSubarrays(int[] nums, int minK, int maxK) {var ans = 0L;int n = nums.length, minI = -1, maxI = -1, i0 = -1;for (var i = 0; i < n; ++i) {var x = nums[i];if (x == minK) minI = i;if (x == maxK) maxI = i;if (x < minK || x > maxK) i0 = i; // 子数组不能包含 nums[i0]ans += Math.max(Math.min(minI, maxI) - i0, 0);}return ans;}
}

795. 区间子数组个数

方法一：一次遍历
思路与算法

一个子数组的最大值范围在$ [left,right]表示子数组中不能含有大于表示子数组中不能含有大于表示子数组中不能含有大于right的元素，且至少含有一个处于的元素，且至少含有一个处于的元素，且至少含有一个处于[left, right]$区间的元素。

我们可以将数组中的元素分为三类，并分别用 000, 111, 222 来表示：

1. 小于leftleftleft，用 000 表示；
2. 大于等于 leftleftleft且小于等于 rightrightright，用 111 表示；
3. 大于 rightrightright，用 222 表示。

那么本题可以转换为求解不包含 222，且至少包含一个 111 的子数组数目。我们遍历 iii，并将右端点固定在 iii，求解有多少合法的子区间。过程中需要维护两个变量：

last1last1last1: 表示上一次 111 出现的位置，如果不存在则为 −1-1−1；
last2last2last2: 表示上一次 222 出现的位置，如果不存在则为 −1-1−1。
如果 last1≠−1last1≠−1last1​=−1

那么子数组若以 iii 为右端点，合法的左端点可以落在 (last2,last1](last2,last1](last2,last1]之间。这样的左端点共有 last1−last2last1−last2last1−last2 个。因此，我们遍历 iii：

如果 left≤nums[i]≤rightleft≤ nums[i]≤rightleft≤nums[i]≤right，令 last1=ilast1 = ilast1=i
否则如果 nums[i]>rightnums[i]>rightnums[i]>right令 last2=ilast2=ilast2=i
然后将last1−last2last1−last2last1−last2

累加到答案中即可。最后的总和即为题目所求。

class Solution {public int numSubarrayBoundedMax(int[] nums, int left, int right) {int res = 0, last2 = -1, last1 = -1;for (int i = 0; i < nums.length; i++) {if (nums[i] >= left && nums[i] <= right) {last1 = i;} else if (nums[i] > right) {last2 = i;last1 = -1;}if (last1 != -1) {res += last1 - last2;}}return res;}
}

Problem: 2488. 统计中位数为 K 的子数组

这个题目的想法来源于795. 区间子数组个数

1. 首先，大于他的就设成1, 小于他的就设成-1。
   这样问题就变成了求包含0的子数组，并且子数组的和为0或者1的子数组的个数。

2. 其次，使用双指针的思想，对于包含k之后的元素，每一个作为数组的终点的话，前面有多少个点可以作为起点。这样就可以使用前缀和 + hash的进行求解。

求前缀和，使用hash统计k之前的数组中前缀和的种类，以及每一种的个数。
最后对于k之后的数组元素，统计前缀和中等于或者比当前前缀和小1的起点个数，也就是种类个数。也就是说，如果当前作为终点，有多少起点可以让前缀和为0或者1。

• Code

class Solution {
public:int countSubarrays(vector& nums, int k) {unordered_mapmp;int n = nums.size();int sum[n + 1];sum[0] = 0;mp[0] = 1;int flag = 0;int ans = 0;for (int i = 0; i < n; i++) {int add = nums[i] > k ? 1 : (nums[i] == k ? 0 : -1);sum[i + 1] = sum[i] + add;   if (add == 0) flag = 1;if (!flag) mp[sum[i + 1]] ++;else ans += mp[sum[i + 1]] + mp[sum[i + 1] - 1];}return ans;}
};