Road to coding interview (Day 1)

Photo by Maranda Vandergriff on Unsplash

Before starting this series, let me briefly introduce its motivation. As fourth-year university student, I have been practicing on LeetCode for two years and have completed more than 250 problems. Unfortunately, I always practice aimlessly, which leads to often forgetting the solution or tips to the AC. It’s really shameful and a waste of time.

As a result, I decided to use a new way to “actually” practice LeetCode. I will gradually complete all the questions on Blind Curated 75. This is a list provided by netizens. It is said that the questions contained most of the question types. I think this is a good start for me, compared to aimless practice as I used to do. I will not aim to complete this list quickly, but to truly understand the solution. This series serves as a record of my learning journey, and everyone who is practicing LeetCode is welcome to learn together by this series.

I will not aim to complete this list quickly, but to truly taste the thought of solving problem. Besides, the reason for writing in English is to practice my poor writing skills.

Finally, let’s start to solve #1 two-sum. Following is problem description:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Because it is guaranteed that the answer is consist of two element and there’s only one answer per set. Suppose we choose the element whose index is 1, first we check if there’s its pair (by subtraction) in hash map. If not, we just push it in hash map for future use.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    vector<int> ans;
    for(int i = 0; i < nums.size(); i++){
        if(mp.find(target - nums[i]) != mp.end()){
            ans.push_back(mp[target - nums[i]]);
            ans.push_back(i);
            break;
        }
        mp[nums[i]] = i;
    }
    return ans;
}

For the first problem in the series, the difficulty seems OK.