美团第一道题~求指导

美团第一道题,不知道错在哪里了,只通过67%,求指导
#include<iostream>   
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
vector<int>a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int k;
cin >> k;
int res = 0;
for (int i = 0; i < n; i++)
{
int j = i + 1;
int sum = a[i], cnt = 1;
while (j < n)
{
sum += a[j];
++cnt;
if (sum%k == 0)
res = max(res, cnt);
j++;
}
}
cout << res << endl;
}
return 0;
}

#美团#
全部评论
输入上万的题目 用scanf不要用cin。 我写的也是暴力O(n^2),AC了 #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> #include <map> #include <set> using namespace std; class Solution{ public: int getKMul(vector<int>& v, int k){ int sum; int mxlen = 0; for (int i=0; i<v.size(); i++) { sum = 0; for (int j=i; j<v.size(); j++) { sum += v[j]; if (sum % k == 0) { mxlen = max(j-i+1, mxlen); } } if (mxlen >= v.size()-i) { break; } } return mxlen; } }; int main(){ int n; cin>>n; vector<int> v; int x; for (int i=0; i<n; i++) { scanf("%d",&x); v.push_back(x); } int k; cin>>k; Solution s; cout<<s.getKMul(v, k)<<endl; }
点赞 回复 分享
发布于 2017-08-31 22:18
你这个最好最坏情况都是O(n^2)的啊。可以根据已经得到的最大长度,跳过一些步骤 比如j=i+res。最好还是看看其他大佬的思路吧。
点赞 回复 分享
发布于 2017-08-31 22:23
时间复杂度过高啊,超时了
点赞 回复 分享
发布于 2017-08-31 22:15
没加任何优化啊,应该会超时吧
点赞 回复 分享
发布于 2017-09-01 00:45
就是超时了,代码复杂度太高了
点赞 回复 分享
发布于 2017-09-01 15:16

相关推荐

11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务