LeetCode_1_TwoSum

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

题目分析：

对一个给定的整数数组和特定的target，数组中存在一对元素的和为target,返回这两个元素的下标。假定每个输入都只有一个确定的输出。
解:
根据题干和e.g， 确保结果中序号小的在前。

Solution:

vector<int> twoSum(vector<int>& nums, int target)
{
    vector<int> rst;
    for (int i = 0; i != nums.size(); i++)
    {
        for (int j = 0/*i+1*/; j != nums.size(); j++)
        {
            if (nums[i] + nums[j] == target)
            {
                rst.push_back(i);
                rst.push_back(j);
                return rst;
            }
        }
    }
    return rst;
}

没什么好说的，最多优化j初始值为i+1;
T(n) = O(n^2);
S(n) = 1;

vector<int> twoSum(vector<int>& nums, int target)
{
    vector<int> rst;
    vector<int>::iterator it_find;
    for (int i = 0; i != nums.size(); ++i)
    {
        int numRst = target - nums[i];
        it_find = find(nums.begin() + (i + 1), nums.end(), numRst);//i+1开始，防止重复查找
        if (it_find != nums.end()) //find numRst
        {
            rst.push_back(i);
            rst.push_back(it_find - nums.begin());
            return rst;
        }
    }
    return rst;
}

基于BR-Tree的std::map::find:　　 T(n) = O(log(n))
则solution2
T(n) = O(n*log(n))
S(n) = 1

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    vector<int> rst;
    for (int i = 0; i != nums.size(); ++i)
    {
        int numRst = target - nums[i];
        if (hash.find(numRst) != hash.end())
        {
            rst.push_back(hash[numRst]);
            //called latest is necessary
            //because hash[numRst] always smaller than i
            rst.push_back(i);
            return rst;
        }
        hash[nums[i]] = i; //insert nums
    }
    return rst;
}

由于unordered_hash::find是不可控的，所以为了避免查找的重复和避免target = nums[i] *2的情况，采用了先查找再插入的做法。

需要注意的是:
unordered_map的find方法 不是基于BR-TREE的查找 而是基于 Direct Hash 和 link-address的。
std::map/multmap的find方法 才是基于BR-TREE的查找。

unordered_map::find: 　　　　　　T(n) = O(1)

solution3:
T(n) = O(n);
S(n) = O(n);