美团第一道题~求指导

输入上万的题目 用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; }

你这个最好最坏情况都是O(n^2)的啊。可以根据已经得到的最大长度，跳过一些步骤 比如j=i+res。最好还是看看其他大佬的思路吧。

时间复杂度过高啊，超时了

没加任何优化啊，应该会超时吧

就是超时了，代码复杂度太高了