01 Two Sum

Description

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

First Thought

The basic solution is pretty simple: traverse nums by i and j and check if their sum equals to the target.

Thar produce the following answer:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        for (int i = 0; i < nums.size() - 1; ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    answer.emplace_back(i);
                    answer.emplace_back(j);
                    return answer;
                }
            }
        }
        return answer;
    }
};

Complexity Analysis

Time complexity

The average time complexity for this $O(n^2)$. The best situation is $O(1)$ and the worst is $O(n^2)$.

Space complexity

$O(1)$, just for i, j and answer.

Hashmap Solution

(It seems that using hash table to find element is a great way to reduce time complexity)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        map<int, int>::iterator in;
        vector<int> answer;
        for (int i = 0; i < nums.size(); ++i) {
                  
            int hope = target - nums[i];
            in = m.find(hope);
            if (in != m.end()) {
                answer.emplace_back(i);
                answer.emplace_back(in->second);
                return answer;
            }
            
            m.insert(pair<int, int>(nums[i], i));
        }
        return answer;
    }
};

Here is the only problem I met: this insert line m.insert(pair<int, int>(nums[i], i)); should be at the end of the loop instead of at the beginning. Or if the target is a even number, then the new number itself is searchable, which lead to a false answer.

Complexity Analysis

Time complexity

The average time complexity for this $O(n)$. The best situation is $O(1)$ and the worst is $O(n)$. The hash map really speed up the searching process, the map.find() function has a time complexity close to $O(1)$.

Space complexity

$O(n)$, hash map has to store all the numbers.

The runtime on leetcode decrease from 590ms to 7ms, really impressive.

penway Wang
penway Wang
Mechanic Technical Director

My research interests include computer vision, artificial intelligence and software engineering. I am a FSAE race car crew member at the same time, designing suspension system.

Next
Previous