人人网2014笔试算法题汇总

1.给出一个有序数组啊，长度为len，另外给出第三个数X，问是否能在数组中找到两个数，这两个数之和等于第三个数X。

我们首先看到第一句话，这个数组是有序的，所以，我们可以定义两个指针，一个指向数组的第一个元素，另一个指向应该指向的位置（这个需要看具体的实现和数组给定的值），首先计算两个位置的和是否等于给定的第三个数，如果等于则算法结束，如果大于，则尾指针向头指针方向移动，如果小于，则头指针向尾指针方向移动，当头指针大于等于尾指针时算法结束，没有找到这样的两个数。

解法一：

#include <iostream>    using namespace std;    int find(int *a, int n)  {      int t = a[0];      int count = 0;      for (int i=0; i<n; ++i)      {          if (count == 0)          {              t = a[i];              count = 1;              continue;          }          else          {              if (a[i] == t)              {                  count++;              }              else              {                  count--;              }          }      }        return t;  }    int main()  {      int n = 10;      int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};        cout<<find(a, n)<<endl;        system("pause");      return 0;  }  

Time Complexity: O(n)

Space Complexity:O(1)

转载请注明原创链接：http://blog.csdn.net/wujunokay/article/details/12209217