Solution using STL binary_search and sort


  • 0

    I solved this O(n lg n) problem before using home grown binary search. This time, I thought what about STL binary_search. Alas, they do not return index :(.

    I tried this:

    class Solution  {
    public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
      vector<int> v;
      for (int i = 0; i<numbers.size(); i++) {
        v.push_back(numbers[i]);
      }
      sort(v.begin(), v.end());
      bool done = false;
      int a, b;
      for (int j = 0; j<v.size() & !done; j++) {
        if (binary_search(v.begin(), v.end(), target - v[j])) {
          done = true;
          a = v[j];
          b = target - v[j];
        }
      }
      vector<int> res;
      for (int k = 0; k<numbers.size() && res.size()<2; k++) {
        if (numbers[k] == a || numbers[k] == b) {
          res.push_back(k + 1);
        }
      }
      return res;
    }    };
    

    It was fun!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.