This is the first time I try Leetcode. Here is the C++ solution to my first Leetcode problem.
We have to find two different indexes, in any order, of two integers which add up to target.
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int * arr = &nums[0]; int size = nums.size(); int size2 = size - 1; for (int i = 0; i < size2; i ++) { for (int ii = i + 1; ii < size; ii ++) { if ((i != ii) && (arr[i] + arr[ii] == target)) { nums.resize(2); arr[0] = i; arr[1] = ii; return nums; } } } return (vector<int>) NULL; } };
This code is very efficient for memory, but at the expense of speed, O(n2). The next code is much faster O(n), but at the expense of memory.
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i(0); std::multimap<int, int> mymap; std::multimap<int, int>::iterator it; for (int num : nums) { mymap.insert(std::pair<int, int>(num, i)); it = mymap.find(target - num); if (it != mymap.end() && it->second != i) { nums[0] = i; nums[1] = it->second; nums.resize(2); return nums; } i ++; } return (vector<int>) NULL; } };