2302. Count the number of subarrays with a score less than k - sliding array - double hundred code

2302. The statistical score is less than K Number of subarrays of

A digital fraction Defined as the sum of arrays multiply Length of array .

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

Here's an array of positive integers nums And an integer k , Please return nums Middle score Strictly less than k Of Number of non empty integer subarrays .

Subarray Is a sequence of consecutive elements in an array .

Example 1：

Input ：nums = [2,1,4,3,5], k = 10
Output ：6
explain ：
Yes 6 The score of the subarray is less than 10 ：

• [2] The score is 2 * 1 = 2 .
• [1] The score is 1 * 1 = 1 .
• [4] The score is 4 * 1 = 4 .
• [3] The score is 3 * 1 = 3 .
• [5] The score is 5 * 1 = 5 .
• [2,1] The score is (2 + 1) * 2 = 6 .
  Be careful , Subarray [1,4] and [4,3,5] Unqualified , Because their scores are 10 and 36, But we need to find that the score of the subarray is strictly less than 10 .

Example 2：

Input ：nums = [1,1,1], k = 5
Output ：5
explain ：
except [1,1,1] The score of each sub array is less than 5 .
[1,1,1] The score is (1 + 1 + 1) * 3 = 9 , Greater than 5 .
So there are 5 The subarray score is less than 5 .

The solution code is as follows ：

long long countSubarrays(int* nums, int numsSize, long long k){
    
    long long count=0;
    long long sum=0,i,j,low=0,high=0;
    long long arrc=0;
    

     while(low<numsSize){
    
     // printf("--lh %d %d",high,low);
        if(high<numsSize){
    
         
            while((sum+nums[high])*(high-low+1)<k){
    
                  
                sum=sum+nums[high];
              
                high++;
                if(high>numsSize-1){
    
                    break;
                }
            }
          }
        
        count=count+high-low;
        sum=sum-nums[low];
        low++;
   
        
     } 
     


   return count;
}

The blogger also wrote a violent Algorithm , It can also solve problems , But the event cost is a little higher ：

long long countSubarrays(int* nums, int numsSize, long long k){
    
    long long count=0;
    long long sum=0,i,j,low=0,high=0;
    long long arrc=0;
    for(i=0;i<numsSize;i++){
    
         sum=nums[i];
         arrc=1;
         if(sum<k){
    
             count++;
         }
         else{
    
             continue;
         }
        for(j=i+1;j<numsSize;j++){
    
            sum=sum+nums[j];
            arrc++;
            if(sum*arrc<k){
    
                count++;
            }
            else{
    
                break;
            }
        }
    }
   return count;
}