1. 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.

Example:

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

Solution(Array):

Use two for-loops: nums[i]+nums[j]==target, time complexity is O(n^2)

Coding(C++):

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

Solution(Hash_table): 

hash_table.find(target - nums[i]) != hash_table.end(), time complexity: O(n)
map::find: Searches the container for an element with a key equivalent to k and returns an iterator to it if found, otherwise it returns an iterator to map::end.


Coding(C++):
 

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector res;
        map hash_table;
        hash_table.clear();
        int n = nums.size();
        for(int i = 0; i < n; i++){
            hash_table[nums[i]] = i;
        }
        for(int i = 0; i < n; i++){
            if(hash_table.find(target-nums[i]) != hash_table.end()){
                if(hash_table[target-nums[i]] > i){
                    res.push_back(i);
                    res.push_back(hash_table[target-nums[i]]);
                    return res;
                }
                if(hash_table[target-nums[i]] < i){
                    res.push_back(hash_table[target-nums[i]]);
                    res.push_back(i);
                    return res;
                }
            }
        }
        return res;
    }
};