Leetcode:1.两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 可以按任意顺序返回答案。

方法一:暴力搜索

基本思想,先让一个迭代器it指向首元素,然后让迭代器it1指向it的下一个元素,之后保持it不变,让it1依次遍历vector,如果找到*it + *it1 == target就将二者的下标it-nums.begin()it1-nums.begin()放入result中。如果it1遍历到末尾还没有找到符合条件的元素,就将it向后移动一步,然后再让it1指向it的下一个元素进行再一次遍历。

vector<int> twoSum1(vector<int>& nums, int target)
{
    vector<int> result;     //用于返回结果的vector容器2
    for(vector<int>::iterator it = nums.begin(); it != nums.end(); ++it)
        for(vector<int>::iterator it1 = it+1; it1 != nums.end(); ++it1)
        {
            if(*it + *it1 == target)
            {
                result.push_back(it-nums.begin());
                result.push_back(it1-nums.begin());
            }
        }
    return result;
}

方法二:哈希表

参考用例:nums = [2,7,11,15], target = 9

vector下标 元素
0 2
1 7
2 11
3 15

将该vector中的下标和元素放入map容器:其中key = 元素,value = vector下标:

key value
2 0
7 1
11 2
15 3

接下来遍历vector,对于vector中的每个元素,查找target - 元素是否在map中,比如该例vector中的第一个元素为2,target = 9,就在map中查找 9 - 2 = 7,显然可以在map中找到该key值,于是程序退出。 但存在一个问题:比如nums = [3,1,2,4], target = 6,可以看出正确结果为:[2,3],但在查找第一个元素时有:6 - 3 = 3,查找到的另一个元素就是他本身,为了避免这种错误还要限定条件:在map中查找到target - 元素时,必须有当前vector下标 != map->value

上述方法中先将vector中的所有元素先拷贝入map容器中再进行遍历,但是显然可以一边查找一边遍历,这样即节省了空间也节省了时间。 具体方法:在将vector中的元素拷贝入map容器前:先在map容器中查找是否存在满足key == target - *it的键值对,找到就将结果拷贝入result退出程序,找不到就将该元素拷贝入map容器:

vector<int> twoSum(vector<int>& nums, int target)
{
    vector<int> result;
    map<int,int> m;
    map<int,int>::iterator mit = m.end();

    for(vector<int>::iterator it = nums.begin(); it != nums.end(); ++it)
    {   
        mit = m.find( target - *it );
        if(mit != m.end())
        {
            result.push_back(it-nums.begin());
            result.push_back(mit->second);
            return result;
        }
        m.insert( make_pair( *it, it-nums.begin() ) );
    } 
    return {};
}

本文章使用limfx的vscode插件快速发布