统计子矩阵（双指针）

解题思路:

/*解题思路*/

/*使用双指针 将A数组中的任意俩列的前缀和看做一个一维数组求解*/

/*在一维数组中 a[n]={a[1],a[2],...,a[n]}; 类似题目 求其中不大于k:9的数组矩阵个数*/

/*那么有俩个指针i j 开始时同时指向a[1]:1 

sum=a[i]加到a[j] 

sum比k小 则j++即j后移

   比k大 则i++即i后移

sum比k大时,此时产生的数组数为(i-j)*/

注意事项:

注意数据要求

参考代码:

#include<bits/stdc++.h>
using namespace std;
int a[520][520];
int s[520][520];  //A数列每行的前缀和 
int main()
{
  long long count=0;
  int k,m,n; cin>>n>>m>>k;
/*输入A数列 同时求前缀和*/
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>a[i][j]; s[i][j]=s[i][j-1]+a[i][j];}
/*数据处理*/
    for(int j1=1;j1<=m;j1++)
        for(int j2=j1;j2<=m;j2++) //j1 j2 表示所要枚举的列数 
    {
        int j=1,sum=s[1][j2]-s[1][j1-1]; //sum表示s数组的累加 
                for(int i=1;i<=n;i++)
            {
                 while(sum<=k && j<=n) {j++; sum+=s[j][j2]-s[j][j1-1];} 
                    count+=j-i;
                    sum-=s[i][j2]-s[i][j1-1]; //当sum>k时,i后移,同时要减去上一个值 
            }
    }
   cout<<count;
  return 0;
}