解题思路:滑动窗口(双指针)
假设区间 [l, r] 的元素之和大于等于k,那么必然有后续区间区间 [l, r+1]、[l, r+2] ……所有这些区间的元素之和必然大于等于k。因此本体可以使用滑动窗口的思路进行解答。
下面给出cpp代码。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, l = 0, r = -1;
long long k, sum = 0, ans = 0;
cin >> n >> k;
vector<int> a(n);
for (int& i : a) {
cin >> i;
++r; //右指针右移
sum += i;
while (sum >= k) { //当区间[l, r]之和大于等于k时
ans += n - r; //后续所有区间都满足要求
sum -= a[l++]; //左指针右移
}
}
cout << ans;
}



京公网安备 11010502036488号