Leetcode 2537. Count the Number of Good Subarrays

[Woodyiiiiiii]

这道题我花的时间有点太久了，虽然最后做出来了很开心。

考虑到递进的思想，每次从左到右加一个nums[i]，可以通过之前存储相同nums[i]的个数，计算pair。容易想到用滑动窗口。

难点在于：

1. 如何规定左右边界的移动
2. 移动后如何计算pair

解决方法：

1. 逆向思维，计算小于k的subarray个数，最后用总数相减
2. 向右移动时，subarray个数增加的数量相当于subarray的长度，因为是从刚加的最右节点开始向左包含的；关键的向左移动时，相当于subarray的起始点变了，终点变成了[r]，所以在计算区间[l,l]到[l, r]之间的subarray，故两者增加的数量同样是r-l。
3. 向左移动时，只需要加r-l是个很有意思的点，因为只计算l+1起始的subarray数目即可，其他的subarray都已经计算过了，所以kCnt在l和r变化时很有意思，代表了subarray数量在边界加一和减一情况下如何变化的。可以拿[1,1,1,1]和4来举例，思考最后的两个1[1,1]在哪里计算过了。

class Solution {
    public long countGood(int[] nums, int k) {
        int n = nums.length;
        long subArrayCnt = (long) n * (n - 1) / 2;
        Map<Integer, Integer> valueMap = new HashMap<>();
        int l = 0, r = 0;
        long cnt = 0, kCnt = 0;
        while (r < n) {
            int value = nums[r];
            cnt += valueMap.getOrDefault(value, 0);
            valueMap.put(value, valueMap.getOrDefault(value, 0) + 1);
            while (cnt >= k && l < r) {
                cnt -= valueMap.getOrDefault(nums[l], 0) > 0 ? valueMap.get(nums[l]) - 1 : 0;
                valueMap.put(nums[l], valueMap.getOrDefault(nums[l], 0) - 1);
                l++;
            }
            kCnt += r - l;
            ++r;
        }
        return subArrayCnt - kCnt;
    }
}

Tips1:

• 注意cnt和kCnt变量的变化，cnt表示区间[l,r]中pair的个数，kCnt表示区间[l,r]中subarray的个数。

又看了下别人的做法，大多数并没有逆向思维进行集合计算，可能是太麻烦了。

那么首先是滑动窗口的移动，那么右边界的停止当然是子数组中[l,r]中pair的数量超过k了，因为l要向左移动，肯定pair的数量减少。

接着计算大于k的子数组数量，这里分两种，可以以左边界为准，或者以右边界为准。以左边界为准的情况下，当pair的数量大于等于k，说明右边界后的n-r个子数组的pair的数量都是大于等于k的，所以可以加入到答案。如下代码：

class Solution {
    public long countGood(int[] nums, int k) {
        int n = nums.length;
        int l = 0, r = 0;
        Map<Integer, Integer> map = new HashMap<>();
        long cnt = 0, ans = 0;
        while (r < n) {
            cnt += map.getOrDefault(nums[r], 0);
            map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
            while (cnt >= k && l < r) {
                cnt -= map.get(nums[l]) - 1;
                map.put(nums[l], map.get(nums[l]) - 1);
                ++l;
            }
            ++r;
        }
        return ans;
    }
}

如果是以右边界为准的情况，则对l进行计算。

所以关键是窗口移动过程中找到符合题目条件的数量的关系。

Tips2:

• 注意要把一些变量设置成long，不然会爆栈。因为我用逆向思维做的时候很容易考虑，但这种情况就忘记了。

类似题目:

• 1759. Count Number of Homogenous Substrings
• 2461. Maximum Sum of Distinct Subarrays With Length K

---

• 2537. Count the Number of Good Subarrays
• Other people's solution