1.两数之和

一、题目：

1.两数之和：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：

二、思路：

遍历数组，看是否存在两数之和为给定的值。

三、代码（C++）：

1.暴力法：两层循环，时间复杂度O(N2)，空间复杂度O(1)

  vector<int> twoSum(vector<int>& nums, int target) {
        int a=0,b=0;        
        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 0;
   }

2.采用unordered_map：时间复杂度O(N)，空间复杂度O(N)，以空间换时间

C++中unordered_map通过hash函数实现，调用find操作时间复杂度为O(1)，但是需要额外的空间，空间复杂度为O(N)

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i=0;i!=nums.size();i++)
        {
            auto iter=hash.find(target-nums[i]);
            if((iter!=hash.end())&&(iter->second!=i))
               return {i,iter->second};
            hash[nums[i]]=i;
        }
        return {0};
}