2302. Count Subarrays With Score Less Than K

Question

The score of an array is defined as the product of its sum and its length.

• For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Solution

第一次在contest中做出hard题目，而且还是超过100%，庆祝一下！（不过因为前一道题做的太久没提交上去……

滑动窗口

数组内全部为正整数，当选择的子数组的尺寸增加时，其乘积是单调递增的。因此可以采用滑动窗口，在循环时维护窗口内数字的和sum和当前的乘积product。

每次将一个新的右侧元素滑入窗口，更新窗口内的sum值，并计算product值。当当前product大于k时，则将左侧的元素滑出窗口，并更新sum和product值。

调整完窗口尺寸后，由于新的right位置可以和前面的每一个子数组组成一个新的数组，因此将count加上当前的left到right的个数即可。

循环结束后返回count。

Code

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0, sum = 0;
        int left = 0, right = 0;
        
        while(right < nums.length){
            sum += nums[right]; //右侧滑入窗口
            long product = sum * (right - left + 1);
            
            while(product >= k){    //当乘积大于k时，左侧滑出窗口
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            count += right - left + 1;  //计算新的right位置可组成的新组合
            right++;
        }
        return count;
    }
}