计数类双指针总结

核心思路

一般是求子数组的问题。

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

例题

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

795. 区间子数组个数

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

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

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

1. 小于$left$，用 000 表示；
2. 大于等于 $left$且小于等于 $right$，用 111 表示；
3. 大于 $right$，用 222 表示。

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

$last1$: 表示上一次 111 出现的位置，如果不存在则为 −1-1−1；
$last2$: 表示上一次 222 出现的位置，如果不存在则为 −1-1−1。
如果 $last1\ne -1$

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

如果 $left\le nums[i]\le right$，令 $last1=i$
否则如果 $nums[i]>right$令 $last2=i$
然后将$last1-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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20