001 Two Sum

From now on, I’d like to solve all algorithm questions on Leetcode one by one to help me pass the job hunting interview in the future, no matter for internship or regular job. 🙂 I also pushed my solution on GitHub.

Let’s get started from the first question: Two Sum.

Question

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea

The main thought is to traverse the whole vector. For each element, check whether the subtrahend exists in the vector. If yes, then return indices of current element and subtrahend. As a result, we need to maintain a structure that could provide us both the value and its index with a good performance. unordered_map is a best choice here.

We’ve not considered another case where the subtrahend doesn’t exist for the moment. What should we do? Think about it, for example, a + b = c where c is our target. Now we get a and check whether b exists. It doesn’t. In order to let us find a when we reach b, we should store a and its index. That’s it. In this way, we can outline the whole traverse.

Solution

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> map;

    for (auto i = 0; i < nums.size(); ++i) {
      const auto key = target - nums[i];

      if (map.find(key) != map.end()) {
        return vector<int>({i, map[key]});
      }

      map[nums[i]] = i;
    }

    return vector<int>();
  }
};

Runtime: 4 ms, faster than 99.70% of C++ online submissions for Two Sum. Memory Usage: 10.1 MB, less than 55.86% of C++ online submissions for Two Sum.

Digression

Three years and four months ago, I submitted a solution with same idea but different code. Its running time is 16ms. Wow. Totally identical idea! This could demonstrate how important writing code efficiently. 🙂 Here is the old solution:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        if (nums.size() == 0) {
            return ret;
        }
        unordered_map<int, size_t> hash;
        for (int i = 0; i < nums.size(); ++i) {
            int left = target - nums[i];
            if (hash.find(left) != hash.end()) {
                ret.push_back(i);
                ret.push_back(hash[left]);
                return ret;
            } else {
                hash[nums[i]] = i;
            }
        }
        return ret;
    }
};

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s