408每日算法——连续子数组长度（2016年清华912）

本文主要是介绍408每日算法——连续子数组长度（2016年清华912），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

连续子数组长度

一、问题描述

　　求一个数组A中连续相同数字的和等于s的最长子数组长度

　　例如A={1,1,2,1,1,1,2,1}，s=3，最终返回3

　　要求算法时间复杂度不超过On)，空间复杂度不超过O(1)

二、算法思路

　　快慢指针：可以设计一个快指针f，一个慢指针s，遍历过程中，如果f.value==s.value，则f++，同时记录一个长度count++，count初值为0，当f.value != s.value时让s=f，同时计算mlength=max（count,mlenght）,然后更新count=0；

三、代码

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int main(){
 5     int n;
 6     scanf("%d",&n);
 7     int A[n];
 8     for(int i=0;i<n;i++){
 9         scanf("%d",&A[i]);
10     }
11     //以上为测试用例的构造，不计入时间复杂度
12     int mlenght=0,count=0,f=0,s=0;
13     while(f<n){
14         if(A[f]==A[s]){
15             f++;
16             count++;
17         }else{
18             s=f;
19             mlenght = max(count,mlenght);
20             count = 0;
21         }
22     } 
23     mlenght = max(count,mlenght);
24     printf("%d",mlenght); 
25     return 0;
26 } 

 四、扩充

　　2018清华912

　　问题描述：单峰向量定义为A[0,n)其中前缀{a₀,a₁,a₂……a_k}严格递增，后缀{a_k+1……a_n-1}严格递减

　　请设计一个时间复杂度为O（logn）的算法找出最大值所在位置k

　　证明算法正确性

　　证明即使在最坏的情况下算法的时间复杂度也不会超过O（logn）

　　提示：看到logn，应该第一时间想到二叉树的高度，而与二叉树类似的是折半查找算法，而证明过程可以尝试使用查找次数来证明

这篇关于408每日算法——连续子数组长度（2016年清华912）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！