1.两数之和

本文主要是介绍1.两数之和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：

思路1：暴力计算，两个for循环解决战斗，但是时间复杂度太高为O(n^2)

思路2：晚上睡觉时思考，能不能将循环拆开，一个循环寻找小于target/2的所有数，记录下标，在另一个循环里面在寻找大于target/2的数，与记录下来的数相加，这样就把嵌套循环拆解开了。白天的时候写了一下，这样还是拆不开，尴尬。

思路2具体代码为：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> fin;
        int one=0;
        int twe=0;
        for(int i=0;i<nums.size();i++){
            if(target/2>=nums[i]) fin.push_back(i);
        }
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<fin.size();j++){
                if(i==fin[j]) continue;
                if(nums[i]+nums[fin[j]]==target){
                    if(i<fin[j])
                      one=i,twe=fin[j];
                    else
                      one=fin[j],twe=i;
                fin.clear();
                fin.push_back(one);
                fin.push_back(twe);
                return fin;
                }
            }
        }
        return fin;
    }
};

运行结果分析：  

执行结果：通过 执行用时：1088 ms, 在所有 C++ 提交中击败了5.10%的用户 内存消耗：10 MB, 在所有 C++ 提交中击败了58.41%的用户 通过测试用例：57 / 57   反思：对于c++的STL没有系统学习，对关键字的应用还停留在基础阶段，许多有用的头文件并不了解。简单来说，题做少了。   优解思路：        使用哈希表，哈希表的containsKey("key")；方法可以直接判断哈希表中是否有这个key值，顺着这个思路，建立哈希表，记录位置i，以及target-nums[i]的值，利用containsKey方法查询nums数组的值在哈希表中存在，没有就将当前target-nums[i]，i存入哈希表中，继续判断下一个数。   知识需求：       1.C++ STL中，哈希表对应的容器是 unordered_map（since C++ 11）。根据 C++ 11 标准的推荐，用 unordered_map 代替 hash_map。       2.unordered_map 容器在<unordered_map>头文件中，并位于 std 命名空间中。       3.哈希表的创建                unordered_map<int,int> map{ {key,value},  {key,value} }                复制其他哈希表unordered_map<int,int> map(other_map);                使用迭代器选择性复制 unordered_map<int,int>map(++other_map.begin(),other_map.end())       4.用到的方法                count(key)查询key值得个数                //除此之外容易混淆的是at(key)和find(key)，at方法会查找key位置并返回对应值，未找到会抛出 out_of_range 异常                //find函数寻找key值，未找到也会返回最后一个key的迭代器。无法使用                //operator[key]，就像数组一样，可以获得对应key的值，不存在就会创建一个，可以像数组一样创建键值对。                insert（）和emplace()添加键值对                erase()删除键值对。       5.哈希表的优势在于key如同数组下标一般可以直接访问和查抄，应用于搜索中，可以节省时间复杂度。 资料来源： C++ STL unordered_map容器用法详解 (biancheng.net) 允许代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> fin;
        for(int i=0;i<nums.size();i++){
           
            if(map.count(nums[i])){
                fin.push_back(map.at(nums[i]));
                fin.push_back(i);
                return fin;
            }
             map.emplace(target-nums[i],i);
        }
        return fin;
    }
};

　　运行效果：

执行用时：12 ms, 在所有 C++ 提交中击败了66.86%的用户 内存消耗：10.5 MB, 在所有 C++ 提交中击败了38.13%的用户 通过测试用例：57 / 57           结果对比：        内存消耗增大和执行用时比起来啥都不是，毕竟现在不像以前，做个超级马里奥贴图还要对称的时代。但是和java代码比起来，这段代码使用java的话只需要1ms，c++需要12ms，但是空间的话java是41.5MB，鱼与熊掌不可兼得，舍空间而取时间者也。

这篇关于1.两数之和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！