leetcode twoSum

1.暴力搜索时间复杂度O(n^2)

#include<iostream>
#include<vector>
using namespace std;

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

注意:

• vector & 一个vector 类型的应用，引用只是另外起了一个名字，如果用局部变量会增加拷贝时间。执行时间160ms, 不用引用大约172ms.
• nums.size() 可以返回nums的大小。
• ret.push_back(i) 向ret里面保存值。

利用哈希，时间复杂度O(n)

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
	{
		vector<int> v(2, 0);
		// val+id
		unordered_map<int, int> hash;
		// we can search num and insert it to hash map at same time
		// and current num must be not in hash map
		for (int i = nums.size(); i--; hash[nums[i]] = i)
		{
			if (hash.find(target - nums[i]) == hash.end())   // 将nums与序号联系起来，直到能找到一对为止
				continue;

			v[0] = i;           // the index from 0 to n-1
			v[1] = hash[target - nums[i]];         // 查找
			return v;
		}

		return v;                   // no answer return {0,0}
	}

};

注意:

• vector v(2, 0) 是一种对vector的初始划；
• unorder_map find的时间复杂度O(1), unorder_map.find 如果key存在，则find返回key对应的迭代器，如果key不存在，则find返回unordered_map::end。
• continue 停止执行后面语句，重新开始循环