学步园

     由于快要找工作，网上去找如何准备工作，找到leetcode,，据说是对面试很有用的题目。题目不多，就打算找工作前拿这些题目复习下以前的知识。一上来没有想到最优的解，先写了个O（nlogn）的算法

struct Node
  {
        int val;
        int index;
        Node(){}
        Node(int v, int idx):val(v), index(idx){}
    };

  bool compare(const Node &lc, const Node &lc)
   {
       return lc.val < lc.val;
  }
 //排序之后，两头扫描判断即可
  class Solution {
  public:
     vector<int> twoSum(vector<int> &numbers, int target) {
          // Start typing your C/C++ solution below
           // DO NOT write int main() function
           vector<Node> a;
           for(int i = 0; i < numbers.size(); i++)
              a.push_back(Node(numbers[i], i + 1));
          sort(a.begin(), a.end(), compare);

          int i = 0;
          int j = numbers.size() - 1;
           while(i < j)
          {    int sum = a[i].val + a[j].val;
               if (sum == target)
              {
                  vector<int> ret;
                  int minIndex = min(a[i].index, a[j].index);
                  int maxIndex = max(a[i].index, a[j].index);
                  ret.push_back(minIndex);
                  ret.push_back(maxIndex);
                 return ret;
              }
               else if (sum < target)
                  i++;
               else
                   j--;
          }
      }
 };

后来看网上的大牛们的解法，发现还有O(n )的算法
http://www.tuicool.com/articles/RBNjuu 通过hashmap 来实现。