蓝桥杯[OJ 1621]挑选子串-CPP-双指针

目录

一、题目描述：

二、整体思路：

三、代码：

---

一、题目描述：

二、整体思路：

1. 要找子串，则必须找头找尾，找头可以遍历连续字串，找尾则是要从头的基础上往后遍历，可以设头为l，尾为r
2. 当子串含有大于等于k的数的数量大于等于m时，这个子串往后拓展的所有子串都符合要求，因此符合条件子串数为n-r+1

三、代码：

#include 
using namespace std;
const int N = 1e4+10;
int arr[N];
int main()
{
  // 请在此输入您的代码
  int n,m,k;cin>>n>>m>>k;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
  }
  int count=0;
  for(int l=1,r=0,ans=0;l<=n;l++,r=l-1,ans=0){//开始先假设[l,r]区间不合法
    while(l>r || (ans1<=n)){
      r++;//尾r每自增一次，子串添加一个项
      if(arr[r]>=m) ans++;//同时要检查子串满足大于等于m的数量是否符合条件             
    }
    if(ans==k) count+=n-r+1;//后面所有项都可生成符合条件的子串
  }
  cout<
  return 0;
}