-4
我正在做3sum问题在leetcode.com3etum LTE leetcode
蛮力的时间复杂度是O(N^3)。
我使用哈希表,所以我认为时间复杂度是O(N^2)。
然而,我仍然有一个TLE(超出时间限制)
我怎样才能加快我的代码?
以下是我的代码
非常感谢!
class Solution public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ANS;
if(nums.size() < 3) return ANS;
map<int,int*> hashtable;
map<int,int*>::iterator it;
vector<int> ans;
for(int i=0;i < nums.size();i++)
{
for(int j=i+1;j < nums.size();j++)
{
it = hashtable.find(nums[j]);
if(it != hashtable.end()) //found target
{
ans.push_back(nums[j]);
ans.push_back((it)->second[0]);
ans.push_back((it)->second[1]);
sort(ans.begin(),ans.end());
ANS.push_back(ans);
ans.clear();
}
else
{
int* temp = new int[2];
temp[0]=nums[i];
temp[1]=nums[j];
hashtable[0-nums[i]-nums[j]]=temp;
}
}
hashtable.clear();
}
sort(ANS.begin(), ANS.end());
ANS.erase(unique(ANS.begin(), ANS.end()), ANS.end());
return ANS;
}};
询问改善工作代码的问题应该在[代码评论](https://codereview.stackexchange.com/)上提问 – NathanOliver
对不起,我将删除该文章 – Frank