解题思路:滑动窗口(双指针)
假设区间 [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; }