[LeetCode Road] Two Sum - Solution/C++

1. Two Sum

Question:

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.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2].

Input: nums = [3,3], target = 6
Output: [0,1]

Source code

Version 1

Idea:
This is my first coding on the LeetCode platform. After reading the problem, my mind's gone blank, I only thought a simple way to solve it. Use two loop to check all numbers, but the time complexity is O(n^2). I knew this method is not efficient!

Time complexity: O(n²)
Space complexity: O(1)

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

Version 2

Idea: So, the source code is refered from online and I added some comments after programming. I heard the Hash Table mechanism at first time. It is a very simple principle, I must remember it! If you want to learn Hash Table, you can see Simple Hash Map.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> returnArray; // return the ans
        map<int, int> mapIndex; // hash table(key:nums[i], value:index)
        map<int, int>::iterator it;
        for(int i = 0; i < nums.size(); i++){
            it = mapIndex.find(target - nums[i]);
            if(it != mapIndex.end()){
                // found it, it means target - nums[i] = it->first
                returnArray.push_back(it->second); // get the value(index) by iterator
                returnArray.push_back(i); // get the current index
                return returnArray;
            }else{
                // add new element
                mapIndex.insert(pair<int, int>(nums[i], i));
            }
        }
        return returnArray;
    }
};

Version 3

Idea:
You also can use unordered_map to implement it.
And, you don't need to declare a vector as a result container to store indexes.

Time complexity: O(n)
Space complexity: O(n)

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