Analysis and comparison of leetcode weekly race + acwing weekly race (t4/t3)

AcWing 57 T3
Leetcode Biweekly 80 T4

Preface

The common ground between the two questions lies in the subarray value The definition of ,LC Multiply the sum of subarrays by their length ,AcWing Divide the sum of subarrays by their length （ Average ）.

analysis - AcWing T3

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
LL s[N];
int stk[N];

int main()
{
    
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
    
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] + x - 100;
    }
    
    int top = 0,res = 0;
    stk[++ top] = 0;
    for(int i = 1; i <= n; i ++)
    {
    
        if(s[stk[top]] > s[i]) stk[++ top] = i;
        else if(s[stk[top]] < s[i])
        {
    
            int l = 0, r = top;
            while(l < r)
            {
    
                int mid = l + r >> 1;
                if(s[stk[mid]] < s[i]) r = mid;
                else l = mid + 1;
            }
            res = max(res, i - stk[r]);
        }
    }
    
    printf("%d\n", res);
    return 0;
}

analysis - LeetCode T4

class Solution {
    
public:

    typedef long long LL;

    long long countSubarrays(vector<int>& nums, long long k) {
    
        LL res = 0, sum = 0;
        for(int i = 0, j = 0; j < nums.size(); j ++)
        {
    
            sum += nums[j];
            while(sum * (j - i + 1) >= k) sum -= nums[i ++];
            res += j - i + 1;
        }
        return res;
    }
};