最快的算法（360面试题）

//问题解决了，谢谢楼上各位大神们。如果按我的想法，正确的代码如下： #include<iostream> #include<vector> #include<unordered_map> using namespace std; pair<int, int> gettwonums(vector<int>& A,const int& K) {  unordered_map<int,int> res;  for (auto &a : A)  {   auto ret=res.insert({ a,1 });   if (ret.second == false)    (ret.first)->second++;  }  for (auto &a :A)  {   auto ret = res.insert({ K - a,1 });   if (ret.second == false)   {    if ((2 * a == K&&res[a]> 1)|| (2 * a != K))     return make_pair(a, K - a);   }  }  return  make_pair(0,0); } int main() {  vector<int> A = { 5,8,6,7,9,2};  auto a = gettwonums(A, 10);  cout << a.first << " " << a.second;  system("pause"); } //根据楼上大神的提示，其实有更简单的方法，代码如下： pair<int, int> gettwonums2(vector<int>& A, const int& K) {  int len = A.size();  unordered_set<int> res;  res.insert(A[0]);  for (int i = 1;i < len;i++)  {   if(res.find(K-A[i])!=res.end())    return make_pair ( A[i], K - A[i]);   res.insert(A[i]);  }  return{ 0,0 }; }

map<int,bool> m; for(i=0;i<n;i++){ if(m[s-a[i]]) return true; else m[a[i]]=1; }

先扫描数组，用hash表存储，再遍历每个数字a，看hash表中是否有s-a即可

力扣两数之和?

hash算法没有问题，只是VS遍历的时候是正序遍历！，完成之前的后会从最后末尾（auto ret = res.insert({ K - a.first,1 }); ）新加入的地方也就是（2，1）的地方继续遍历，这样写在VS上会永远遍历下去知道找到合适的返回，因为你在一直加入新的元素。而在gcc中则是从hash的末尾逆序遍历，这样就不存在新加入的元素导致无限遍历。最后对刚刚的误会说声抱歉~。

用hash就可以，先遍历放入hash，然后在判断。或者可以利用hash的思想，应该还要快一点。 求数组里最大和最小的，然后用s减去最大，最小。得到min，max。这两个减一下就是可以作为hash表的长度，做一个和hash差不多的数组T，然后遍历L，如果在最大和最小之间，就可以放到T里面，T的下标就是 L[i]-s+min 这样遍历完了之后就把L满足条件的都放到T里了，在遍历一次，看相加是否为s就好了

不可能吧，一般都是有序数组才能达到o(n).

#include<iostream> #include<vector> #include<unordered_map> using namespace std; pair<int, int> gettwonums(vector<int>& A,const int& K) { unordered_map<int,int> res; res.rehash(A.size() * 2); for (auto &a : A) { auto ret=res.insert({ a,1 }); if (ret.second == false) (ret.first)->second++; } for (auto a :res) { auto ret = res.insert({ K - a.first,1 }); if (ret.second == false) { if (2 * a.first == K&&a.second > 1) return make_pair(a.first, K - a.first); else if (2 * a.first != K) return make_pair(a.first, K - a.first); } } return make_pair(0,0); } int main() { vector<int> A = { 5,8,6,7,9}; auto a = gettwonums(A, 10); cout << a.first << " " << a.second; system("pause"); } 输出2,8.。。。。不知道为啥