做题时一定要注意数据范围 数据范围的不同可能导致代码的某些地方不同 题目数据已加强$,$再次交原来的码看会不会被卡掉

第一种做法 $:$ 暴力枚举

也是赛时写得最多的做法： 用两层循环 分别枚举 $l$ 和 $r$ 找到满足的区间 然后答案加一（这里用了前缀和做了预处理）

前缀和$:$

for(int i = 1; i <= n; i++)
{
    sum[i] = sum[i - 1] + a[i];
}

$sum[i]$ 记录的是前 $i$ 项的和 例如 $sum[5]$ 代表前 $5$ 个数的和 因此我们如果想要算区间 $l$ $-$ $r$ 的和 我们可以用前缀和数组表示: $sum[r]$ $-$ $sum[l - 1]$

该解法的时间复杂度为$o(n * n)$ 因此过不了该题

#include<stdio.h>

long long int a[100005], sum[100005];
int main()
{    
    int n, k;
    
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
	}
	
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	
	long long cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = i; j <= n; j++)
		{
			if(sum[j] - sum[i - 1] >= k) cnt++;
 		}
	}
	
	printf("%lld",cnt);

	return 0;
}

第二种做法 $:$双指针

也是第一种做法的优化: 第一种做法我们是两层循环枚举 $l$ 和 $r$找答案 那我们是否可以通过枚举 $l$ 或 $r$ 来找到答案？ 我们发现通过前缀和的维护，我们要找的和是单调的，比如我们通过 $l$ 找 $r :$ 假如找到了第一个满足条件的 $r$ 那后面的 $r - n$ 都将会满足条件 因此答案加上 $(n - r + 1)$

例如 $:$ 当 $n = 5$ 时 我们发现 区间 $1 - 3$ 的和已经大于等于 $k$ 那么同理区间$1 - 4$和区间 $1 - 5$ 也将会满足 则答案加上 $(n - r + 1)$ 也就是 $3$

代码如下 $:$

#include<stdio.h>

long long int a[100005], sum[100005];
int main()
{    
    int n, k;
    
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
	}
	
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	
	long long cnt = 0;
	int r = 1;
	for(int l = 1; l <= n; l++)
	{
		while(sum[r] - sum[l - 1] < k && r <= n) r++;
		
		if(r > n) break;
		cnt += (n - r + 1);  
	}
	
	printf("%lld",cnt);

	return 0;
}

核心代码 $:$

for(int l = 1; l <= n; l++)
{
	while(sum[r] - sum[l - 1] < k && r <= n) 
    {
        r++;
    }
		
	if(r > n) break;
	cnt += (n - r + 1);  
}

我们通过枚举 $l$ 来找到第一个满足的 $r$ 如果找到 那么答案加上 $(n - r + 1);$ 同时我们 的 $r$ 也不需要变化

如果没找到 则 $r > n$ 那么以后的任何区间都不会满足条件 则程序结束

该做法的思想为双指针 $:$ 由于我们要找的数据具有单调性 所以当 $l$ 向右移动时 $r$ 只会向右或不动 所以我们可以来固定 $l$ 找 $r$

第三种做法 $:$ 二分查找

先了解二分查找可以干什么 $:$ 它可以在一组有序(升序/降序)的数据中查找一个元素，它是一种效率较高的查找方法。 例如 $:$

1 4 7 10 11 20 25 47

我们可以通过二分查找 找到大于 或 大于等于 某个元素的第一个下标 例如我们可以用二分查找到大于 $20$ 的第一个下标为 $7$ 也可以用二分查找找到大于等于 $20$ 的第一个下标为 $6$

由于我们的前缀和数组是单调(升序)的 因此我们可以枚举 $l$ 通过二分查找找到 $r$

代码如下 $:$

#include<stdio.h>

long long int a[100005], sum[100005];
int main()
{    
    int n, k;
    
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
	}
	
	for(int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	
	long long cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		int l = 1, r = n, mid;
		while(l < r)
		{
			mid = (l + r) / 2;
			if(sum[mid] >= sum[i - 1] + k) r = mid;
			else l = mid + 1;
		}

		if(sum[l] - sum[i - 1] >= k) cnt += (n - l + 1);
		
	}
	
	printf("%lld",cnt);
	return 0;
}

核心代码 $:$

while(l < r)
{
	mid = (l + r) / 2;
	if(sum[mid] >= sum[i - 1] + k) r = mid;
	else l = mid + 1;
}

因为前缀和数组代表的是前 $i$ 项的和 因此想要从 $i$ 开始 找到 右边的第一个 $r$ 我们要找大于等于 $sum[i - 1] + k$ 的第一个数

时间复杂度为 $o(n * log(n))$