InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Write a function that, when passed a list and a target sum, returns, efficiently with respect to time used, two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return (-1, -1). |
|
Answer» #include <stdexcept> #include <iostream> #include <vector> #include <utility> #include <unordered_map> using NAMESPACE std; class TwoSum { public: static pair<INT, int> findTwoSum(const std::vector<int>& list, int sum) { unordered_map<int,int> s; for (size_t i = 0; i < list.size(); ++i) { auto j = s.find(sum - list[i]); if (j != s.end()) return make_pair(i,j->second); s[list[i]] = i; } return make_pair(-1, -1); } }; #ifndef RunTests int main(int ARGC, const CHAR* argv[]) { std::vector<int> list; list.push_back(3); list.push_back(1); list.push_back(5); list.push_back(7); list.push_back(5); list.push_back(9); pair<int, int> INDICES = TwoSum::findTwoSum(list, 12); cout << indices.first << '\n' << indices.second; return 0; } #endif Output is: 3 2 |
|