关于LeetCode的初探----两数之和

题目大意：给定一个数组以及某个整数和n，应当在数组中找到两个数和为n，并且返回对应的数组下标

解题思路：

1.暴力法

2.利用map（分为两种思路，一为先循环定制好map，然后在map中查找，二为在每次设定键值对之前在map中查找是否存在符合条件的键值对）

1. 暴力法

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 vector<int> {i,j};
        return vector<int> {};
    }
};

2.利用map的两种方法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hash;
        for(int i=0;i<nums.size();i++)//存键值对
            hash[nums[i]]=i;
        for(int i=0;i<nums.size();i++)
            {
                int temp=target-nums[i];
                if(hash.find(temp)!=hash.end()&&hash[temp]!=i)//确保存在且不重复
                    return vector<int>{i,hash.find(temp)->second};//我们需要的不是元素是下标
            }
        return vector<int>{};//表示没有找到，返回空的数组
    }
};

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

经过比较，暴力法自不必说，时间复杂度为O(n²)，不是我们所期望的，第二种方法的时间复杂度都是O(n)，但相比之下，实现2更为巧妙（利用了map中的元素不会相同减少了判断），同时，仅仅一个循环也更加的快，超推荐！

附：关于hash.find()的说明，其返回值是被查找元素的位置，如果没有就返回map.end()，当然，这里的map可以任意定义。

小菜鸡第一次写博客，如有理解有误的地方，请多多包涵。