leetcode 3sum c++解法超时# JobHunting - 待字闺中
s*n
1 楼
用了unordered_map来check第三个数是否存在，如果unordered_map是O（1），那整个
算法复杂度是O（n＊n）啊，为什么过不了large test？
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(),num.end());
unordered_map m;
for (size_t i=0; i(num[i],true));
}
vector > solution_set;
for (size_t i=0; i
for (size_t j=i+1; j
if (j+1 ==num.size()){//j is the last element
break;
}
if (0-number_1-number_2 < num[j+1]){
break;
}
if (m.find(0-number_1-number_2)!=m.end()){
vector solution (3);
solution[0] = number_1;
solution[1] = number_2;
solution[2] = 0-number_1-number_2;
solution_set.push_back(solution);
}
}
}
vector > unique_solution_set;
for (size_t i = 0; i < solution_set.size(); ++i){
vector potential_solution = solution_set[i];
bool flag = true;
for (size_t j = 0; j < unique_solution_set.size(); ++j){
vector verified_solution = unique_solution_set[j];
if (potential_solution[0] == verified_solution[0] &&
potential_solution[1] == verified_solution[1] &&
potential_solution[2] == verified_solution[2]){
flag = false;
break;
}
}
if (flag == true){
unique_solution_set.push_back(potential_solution);
}
}
return unique_solution_set;
}
};
算法复杂度是O（n＊n）啊，为什么过不了large test？
class Solution {
public:
vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(),num.end());
unordered_map
for (size_t i=0; i
}
vector
for (size_t i=0; i
for (size_t j=i+1; j
if (j+1 ==num.size()){//j is the last element
break;
}
if (0-number_1-number_2 < num[j+1]){
break;
}
if (m.find(0-number_1-number_2)!=m.end()){
vector
solution[0] = number_1;
solution[1] = number_2;
solution[2] = 0-number_1-number_2;
solution_set.push_back(solution);
}
}
}
vector
for (size_t i = 0; i < solution_set.size(); ++i){
vector
bool flag = true;
for (size_t j = 0; j < unique_solution_set.size(); ++j){
vector
if (potential_solution[0] == verified_solution[0] &&
potential_solution[1] == verified_solution[1] &&
potential_solution[2] == verified_solution[2]){
flag = false;
break;
}
}
if (flag == true){
unique_solution_set.push_back(potential_solution);
}
}
return unique_solution_set;
}
};
