力扣--两数之和--C++版

力扣热题100-----[1]两数之和---C++版


题目要求

//给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 
//
// 你可以按任意顺序返回答案。 
// 示例 1: 
//
// 
//输入:nums = [2,7,11,15], target = 9
//输出:[0,1]
//解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
// 
//
// 示例 2: 
//
// 
//输入:nums = [3,2,4], target = 6
//输出:[1,2]
// 
//
// 示例 3: 
//
// 
//输入:nums = [3,3], target = 6
//输出:[0,1]
// 
//
// 
//
// 提示: 
//
// 
// 2 <= nums.length <= 103 
// -109 <= nums[i] <= 109 
// -109 <= target <= 109 
// 只会存在一个有效答案 

常规基本解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //unordered_map 内部实现了哈希表 可以用于快速搜索
        // 头文件引入include<unordered_map>
        unordered_map<int,int> hashtable;

        for (int i = 0 ; i<nums.size();++i){
            //auto 自动类型
            // hashtable.find(target - nums[i]) 返回的是一个迭代器,通过second属性来获取值
            //没找到就返回unordered_map::end
            auto it = hashtable.find(nums[i]);
            if(it != hashtable.end()){ //存在补数
                //it->second 此时表中查到数据的原下标 value
                // i 此时数据的下标
                // it->first 为key
                // cout<<it->first;
                return {it->second, i };
                // return [it->second, i];

            }
            //把补数塞进表内,便于查找
            hashtable[target - nums[i]] = i;
        }
        //return {} c++11的问题
        // 花括号{}代表一个空的vector<vector<int>>,size为0
        return {};
    }
};

哈希表解法过程

​ 该题的解法过程与之前的Java版本类似

​ 首先通过unordered_map<>创建一个哈希表;

​ 之后将补数塞进哈希表内

hashtable[target - nums[i]] = i;

​ 通过 hashtable.find(nums[i])寻找当前数所需要的补数

  • auto 自动类型,根据赋值的类型自动转换
  • hashtable.find() 如果找到结果,返回的是一个迭代器,通过second(value)属性来获取值,没找到就返回unordered_map::end
  • it != hashtable.end()判定是否寻找到了值

通过这个题我学到的知识点

  • 在C++11中,return{}可以直接返回一个空数组[],

    那么return{3,4,5} -> [3,4,5]

  • unordered_map 是一个C++的容器,内部采用的是hash表结构,拥有快速检索功能,可能会经常使用。

    参考博客:https://blog.csdn.net/lizhengze1117/article/details/96728468

  • Vector作为函数返回值、可以用于函数接收参数

    ​ 使用vector<>来定义,大概是规范化使用,用于修改方便吧

    vector<int>& nums 这里的&是引用的意思,这样就可以修改实参。


短期计划

​ 虽然Java,C++,Python,C#,都会一点,但是确实没有一个算得上是精通的,所以希望通过算法的练习来渐渐熟悉C++ STL的使用,java还是用来用作开发语言。

上一篇:重新认识Java--HashMap、HashTable和ConcurrentHashMap


下一篇:散列查找