首页 > 其他分享 >2302. 统计得分小于 K 的子数组数目(双指针,贡献法,子数组问题)

2302. 统计得分小于 K 的子数组数目(双指针,贡献法,子数组问题)

时间:2023-12-03 10:11:46浏览次数:29  
标签:right nums int res 2302 数组 指针 left

 

枚举子数组问题,常见有固定一个点,枚举另一个端点,还有枚举中间点。

本题使用双指针算法,对右端点进行枚举,每次累加[l, r]区间内,所有以右端点为结尾的子数组对答案的贡献度,也就是长度 r- l + 1

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        res = left = s = 0
        for right, val in enumerate(nums):
            s += val
            while s * (right - left + 1) >= k:
                s -= nums[left]
                left += 1
            res += right - left + 1
        
        return res

 

标签:right,nums,int,res,2302,数组,指针,left
From: https://www.cnblogs.com/zk6696/p/17872630.html

相关文章

  • react中数组的操作
    添加元素:你可以使用push方法来在数组的末尾添加一个元素,或者使用unshift方法来在数组的开头添加一个元素。你也可以使用concat方法或者扩展运算符...来合并两个数组。letarr=[1,2,3];arr.push(4);//arrisnow[1,2,3,4]arr.unshift(0);//arrisnow[0,1,2,3,......
  • PTA|C语言|数组练习题
    --------------------------------------------------------------------------------求最大值及其下标本题要求编写程序,找出给定的n个数中的最大值及其对应的最小下标(下标从0开始)。输入格式:输入在第一行中给出一个正整数n(1<n≤10)。第二行输入n个整数,用空格分开。输出格式:在一行......
  • 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II
    977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II 977.有序数组的平方思路:分别从数组的左,右向另一侧/中间趋近,新建立一个数组接收(有序序列)(动态地在过程中接收数据)  拓展为各个任务分配工作指针,形成多指针有序数字序......
  • 代码随想训练营第五十二天(Python)| 300.最长递增子序列、674. 最长连续递增序列、718.
    300.最长递增子序列classSolution:deflengthOfLIS(self,nums:List[int])->int:iflen(nums)<=1:returnlen(nums)#dp数组代表以nums[i]结尾的最长递增子序列长度为dp[i]dp=[1]*len(nums)res=1......
  • 数状数组
    1.循环右移,老套路了,直接开2n数组然后利用树状数组进行区间求和和单点修改,每次减去之前以及出现过的值Problem-E-Codeforces1#include<bits/stdc++.h>2usingnamespacestd;34constintN=1e6+10;56intt;7intc[N*2];8intsum(intx)9{......
  • 【差分数组】我的日程安排表
    一、我的日程安排表I题目链接:我的日程安排表I实现一个MyCalendar类来存放你的日程安排。如果要添加的日程安排不会造成重复预订,则可以存储这个新的日程安排。当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生重复预订。日程可以用一对整数......
  • 双指针问题
    1.双指针暴力超时,优化方案Problem-D-Codeforces当数组中只存在1和2的值的时候我们可以考虑用二分去优化,我们可以找到数组中最后一个1的值,前面都是1和2的话我们可以通过最后一个1去灵活地凑出第一个数到最后一个1的数的和中间的任意一个值(划重点)当然我们要尽可能凑出来......
  • 《力扣面试150题》题单拓展——双指针
    《力扣面试150题》题单拓展——双指针1.基础知识为什么双指针会正确?不会漏掉搜索空间数组nums递增排序,假设共8个元素假设由于搜索空间i<j的限制,只搜索右上角白色倒三角空间,一开始,我们检查右上方单元格(0,7),即计算A[0]+A[7],与target进行比较。如果不相等的话,则要么大......
  • 【C语言】【二级】移动一维数组中的内容;若数组中有n个整数,要求把下标从0到p的数组元
    题目请编写函数fun,函数的功能是:移动一维数组中的内容;若数组中有n个整数,要求把下标从0到p(含p,p小于等于n-1)的数组元素平移到数组的最后。例如,一维数组中的原始内容为:1,2,3,4,5,6,7,8,9,10;p的值为3。移动后,一维数组中的内容应为:5,6,7,8,9,10,1,2,3,4。考点一维数组、......
  • 通过Span实现高性能数组,实例解析
    Span<T>是C#7.2引入的一个强大的数据结构,用于表示内存中的一块连续数据。它可以用于实现高性能的数组操作,而无需额外的内存分配。在本文中,我将详细介绍如何使用Span<T>来实现高性能数组操作,并提供一些示例代码来说明其用法。什么是Span?Span<T>是System.Memory命名空间......