leetcode 1两数之和

这篇具有很好参考价值的文章主要介绍了leetcode 1两数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 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]

解析

这道题是leetcode中的第一道题,应该也是很多人梦开始的地方,这道题可能有些人觉得他很简单,直接两层for循环就可以解决的事情,其实这是一道典型使用hash表解决的题目
使用那种哈希表来解决?
哈希表有三种实现方式,第一种使用数组来完成,第二种使用set集合来完成,第三种使用map来操作
在这里很明显是需要是要使用map来解决
map有三种实现方式
map和multimap底层使用红黑树来实现,还有一种就是使用unrodered_map来实现,这个的效率是最高的,增删改查的效率都是o(1)
为什么想到采用hash法来解决这道题
我们要查询一个元素是否在之前的遍历中是否出现过,避免一个元素的重复查询,通过这种方式来降低时间复杂度,就要第一时间想到哈希法文章来源地址https://www.toymoban.com/news/detail-790921.html

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //定义一个map来存放两个数据,这里使用到map来操作减低了复杂度,因为unordered_map的查找效率等等都是o(1)
        unordered_map<int,int> temp;
        for(int i=0;i<nums.size();i++){
            int res=target-nums[i];
            auto it=temp.find(res);
            if(it!=temp.end()){
                return {it->second,i};
            }
            // map存储的就是键对值,所以插入的时候插入的是pair对组
            temp.insert(pair<int,int>(nums[i],i));
        }return {};
    }
};
```
#  通过
leetcode 1两数之和,# 我得leetcode之路,leetcode,哈希算法,散列表

到了这里,关于leetcode 1两数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 解决两数之和问题的哈希表方法

    在给定整数数组中寻找和为目标值的两个整数,并返回它们的数组下标。通过暴力枚举或哈希表方法,时间复杂度小于O(n^2)。Java和C++代码解决方案。

    2024年02月01日
    浏览(48)
  • leetcode - 01两数之和

    时间复杂度读 O ( n 2 ) O(n^2) O ( n 2 ) 空间复杂度 O ( 1 ) O(1) O ( 1 )

    2024年02月12日
    浏览(62)
  • Leetcode 1.两数之和

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

    2024年04月10日
    浏览(38)
  • leetcode 1两数之和

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

    2024年02月01日
    浏览(59)
  • [LeetCode] 1.两数之和

    给定一个整数数组 nums 和一个目标值 target ,请你在该数组中找出和为目标值 target 的那两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 示例 2: 示例 3: 提示: 2 =

    2024年02月05日
    浏览(54)
  • LeetCode两数之和

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

    2024年02月11日
    浏览(43)
  • leetcode刷题:两数之和

    面试造火箭,工作拧螺丝,话虽如此,背背八股文,刷刷算法题,也可以提高自己的编程素养,一切目的是为了上岸,在此就不咬文嚼字,追求茴香豆的茴有几种写法了,换句话说,就是不考虑时间或者空间复杂度,直接采用最容易想到的常规手段。 题目 给定一个整数数组

    2024年04月28日
    浏览(36)
  • leetcode--1--两数之和

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

    2024年04月25日
    浏览(35)
  • day6 哈希 有效的字母异位词 两个数组的交集 快乐数 两数之和

    - day5周日休息 --- 哈希表 - 什么时候用     - 需要记录对比数据,判断数据是否在集合里面 - 哈希三种形式     1. 数组         - 记录一个数         - 已知长度,belike 26个字母         - 已知最大长度,且长度较小,belike 1 = num = 1000     2. set         - 记录一个数

    2024年02月16日
    浏览(66)
  • leetcode_001两数之和

    1. 题目 两数之和 2. 题意 找到数组中和为给定值的两个值的坐标。 3. 题解 3.1 暴力 两重循环,直接列举出来。 3.2 哈希表 查找 hash(val) 是否存在,在表中则取出得到答案;否则将当前位置存入表中 hash(target - val) 。

    2024年02月17日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包