1. Two Sum

problem description

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

algorithm thought

这题可以用3种解法。如果是刚接触算法的，最开始想到的方法肯定是两个循环便利求解。

第二种方法就是先排序，然后使用左右指针逼近，求得结果。这种方法也是之后three sum和four sum的基础，但是这里需要返回的是原来数组的下标值，而不是数字本身。所以这里用这种方法得不到答案

第三种方法是利用hash表一遍遍历得到解答，使用hash表保存target-之前的值。处理一个数据的时候首先在hash表中对比以下，如果存在就返回。这种方法在之后很多能一次便利出结果的解答里都会出现，用一个hash表保存前面遍历的状态，之后拿到状态再来对比。

code

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

//third
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> ma;   //the value represented by map.first is target-nums[i]
                                     //the value represented by map.second is index
        for(int i=0;i<nums.size();++i){
            if(ma.count(nums[i]))
                return {ma[nums[i]],i};
            else
                ma[target-nums[i]]=i;
        }
        return {};
    }
};

algorithm analysis

第一种方法有两个循环每个循环运行n次，时间复杂度O(n平方)

第二种方法这里没有给出代码，根据算法思想，首先排序之后再左右指针。排序最快的时间复杂度是O(nlgn)，左右指针便利时间复杂度是O(n)，最后时间复杂度是O(nlgn)

第三种方法使用hash表解答。code中用的是unordered_map。一定要注意在c++中unordered_map和map之间的区别，前一个底层是hash表，后一个底层是红黑树。如果需要O(1)的插入，查找。需要使用unordered_map。

code中有一个循环，循环中进行的操作只有查找和插入hash，时间都是O(1)，所以最后时间复杂度是O(n)