Day62 | 灵神 | 滑动窗口：统计得分小于K的子数组数目

2302.统计得分小于K的子数组数目

2302. 统计得分小于 K 的子数组数目 - 力扣（LeetCode）

这道题目虽然是hard，但是通过前几天的做题，我个人觉得这道题反而比2962. 统计最大元素出现至少 K 次的子数组 - 力扣（LeetCode），因为这道题的统计子数组的方式比2962这道题好想很多

思路：

还是那个核心思路，固定右端点，遍历右端点，找左指针收缩的条件，这道题的收缩条件很简单，就是左右指针区间[l,r]内的数的和再乘以数量得到的数大于等于k就行。

所以思路比较简单。

另外统计子数组方式就是(r-l+1)，即区间长度

举例：

[2,1,4,3]如果这四个数满足条件的话，那么[1,4,3]，[4,3]，[3]那必然符合，那所有的子数组数量就是(r-l+1)=4咯

下面是笔者的代码，这个代码会有一个测试用例超时，咱们来看看有什么地方可以进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long res=0;
        long long l=0;
        long long nums_sum=0;
        for(int i=0;i<nums.size();i++)
        {
            int sum=0;
            for(int j=l;j<=i;j++)
                sum+=nums[j];
            nums_sum=sum*(i-l+1);
            while(nums_sum>=k)
            {
                nums_sum/=(i-l+1);
                nums_sum-=nums[l];
                l++;
                nums_sum*=(i-l+1);
            }
            res+=(i-l+1);
        }
        return res;
    }
};

1.while循环中每次都要乘除乘除，有很多的重复计算

改为用sum记录[l,r]区间的和，while条件改为乘法的表达式，这样左指针移动后只需要进行sum的加减就行

1
2
3
4
5
while(sum*(i-l+1)>=k)
{
	sum-=nums[l];
	l++;
}

2.每次都用for循环计算[l,r]区间的和，这个没啥必要，因为左指针往右收缩的时候就已经对sum进行了修改，我们只需要加上右端点，就能得到区间的和，而不是每次都要计算

1
2
3
4
5
int sum=0;
for(int j=l;j<=i;j++)
	sum+=nums[j];
改为
sum+=nums[i];

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long res=0;
        long long l=0;
        long long sum=0;
        for(int i=0;i<nums.size();i++)
        {
            //计算[l,r]的和
            sum+=nums[i];
            //左指针收缩使得子数组满足题目条件
            while(sum*(i-l+1)>=k)
            {
                sum-=nums[l];
                l++;
            }
            //更新答案
            res+=(i-l+1);
        }
        return res;
    }
};