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;
}
};
