所谓的子数组就是区间，要求找到所有满足条件的区间。如果用暴力算法枚举区间，复杂度较高无法满足要求。
乘法末尾0的数量是比较常见的问题，本质是所有相乘数字中因子2和因子5的数量。另外，如果一个区间[i,j]满足乘积不少于x个0的要求，那么区间内2和5因子数量一定均大于x，同时如果拓展这个区间，即在其左右增加任意个元素，一定也满足乘积不少于x个0的要求。
解题方法：前缀和+双指针。前缀和用于统计区间内因子2和5的数量。双指针确定以j为右端点，且满足条件的最短区间。如果这个区间是 [i,j]，那么[1,j],[2,j]........[i-1,j]，一定也满足条件。
前缀和和双指针算法复杂度均为O(n），此算法复杂度为O（n）。
class Solution {public:int getSubarrayNum(vector<int>& a, int x) {int i,j,n=a.size(),ans=0,mod=1e9+7;vector<int> sum2(n+5,0),sum5(n+5,0);/**< sum2,sum5，统计到第i个元素时，有多少个因子2，因子5 */for(i=0;i<n;i++){int s2=0,s5=0;/**< 拆分统计数量 */while(a[i]>0&&a[i]%2==0)s2++,a[i]/=2;while(a[i]>0&&a[i]%5==0)s5++,a[i]/=5;sum2[i+1]=sum2[i]+s2,sum5[i+1]=sum5[i]+s5;}i=1,j=1;/**< 双指针确定以[i,j]区间为以j为右端点满足条件的最小区间，那么显然左端点<=i的一定也都满足条件 */while(sum2[j]<x||sum5[j]<x)j++;/**< 先找到第一个满足条件的右端点j */while(j<=n){/**< while判断如果i向右走一格是否仍满足条件x，找到满足条件最大的i值 */while(sum2[j]-sum2[i]>=x&&sum5[j]-sum5[i]>=x)i++;ans=(ans+i)%mod;/**< [i,j]区间满足条件，[1...i-1,j]一定也满足条件，因此有i个区间 */j++;}return ans;}};
如果觉得《连续子数组数量-腾讯音乐娱乐集团校园招聘技术类岗位》对你有帮助，请点赞、收藏，并留下你的观点哦！
