Now it’s the time to go through LeetCode as algorithm problems are indeed very important when I’m graduating soon. I was pretty confident with my algorithm skills before look at the first easy problem on LeetCode. This problem is called Two Sum. Probably most of you guys have seen it. The best and fast solution is a bit tricky and I’m going to list a couple of good solutions to this problem. Some of them are collected from the website. There will be a source reference attached to each of those for your information.
Problem Description:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
This problem seems easy at the first glance (even marked as “easy”). My first C++ implementation is brute-force as I believe many people also will do so. Let’s have a look.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result(2, 0);
for (int i=0; i<nums.size(); i++) {
for (int j=i+1; j<nums.size(); j++) {
if (nums[j] == target - nums[i]) {
result[0] = i;
result[1] = j;
}
}
}
return result;
}
};
Generally, there are just two for loops and iterate over each element to end up with the target value. It is simple. First time I use Vector this data type in C++. It can be seen as an enhanced version of normal array. By the way, I think it is also good for my C++ skills. I will solve these algorithm problems by using C++ as well as Go. Why Go? Many people consider it as the future programming language. So, fire it away!
Generally, there are just two for loops and it iterates over each element to end up with the target value. It is simple. First time I use #Vector this data type in C++. It can be seen as an enhanced version of normal array. By the way, I think it is also good for my C++ skills. I will solve these algorithm problems by using C++ as well as Go. Why Go? Many people consider it as the future programming language. So, fire it away!
Beyond that, LeetCode friendly shows hints for better solutions. I was scratching my head to comp up with some ideas. There is a very general rule for every single algorithm problem, namely, by #Trading space for speed. New data structure is allowed if it speeds up our application. I had a thought that it can jump over some elements if one of these two numbers is already greater than the target value but obviously this does not help to the speed.
So look into the solution, they provide three ways to deal with it. The first one is brute-force version. Secondly, it comes to hash table implementation. The third is to further implement the hash table such that only one pass can be done. “Pass” here means one iteration over the whole array (vector in C++). Take a look how to do it.
The answer below shows by using the push_back() function an element can be added to the tail of the vector.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>sum;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[j]==target-nums[i]){
sum.push_back(i);
sum.push_back(j);
return sum;
}
}
}
}
};