find_sum.cc

#include <algorithm>
#include <iostream>
#include <vector>

std::pair<int,int> find_sum(int sum, std::vector<int>  aray)
  {
    std::vector<int> temp = aray;
    std::sort(temp.begin(), temp.end()); // Ascending order
    int i1; int i2;
  
      // N * log(N)
      for(int i = 0; i < temp.size(); i++)
      {
        int remaining = sum - temp[i];
  
        auto it = std::find_if(temp.begin()+i, temp.end(),[=](int e) { return e == remaining;}); 
  
        if(it != temp.end())
        {
          i1 = i;
          i2 = it - temp.begin();
          break;
        }
  
      }
  
      // find the original index 2*log(N)
    auto it = std::find_if(aray.begin(), aray.end(), [=](int x){ return temp[i1] == x;});
      i1 = it - aray.begin();
  
    it = std::find_if(aray.begin(), aray.end(), [=](int x){ return temp[i2] == x;});
    i2 = it - aray.begin();
  
      // 2*log(N) + N*log(N) ~ N*log(N) 
      return std::make_pair(i1,i2);
  }
  
  int main()
  {
     std::vector<int> test = {1,2,5,4,8,6};
      
     auto p = find_sum(5, test);
     
     std::cout << "(" << p.first << "," << p.second << ")\n";
     
      
  }