LeetCode:每日一题(2020.4.6)
发布日期:2021-06-30 15:45:58
浏览次数:3
分类:技术文章
本文共 1289 字,大约阅读时间需要 4 分钟。
两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解答
一、暴力法 时间复杂度:O(n²)
思路:使用双层for循环,外层遍历数组,寻找当前元素与target的差值,内层循环遍历整个数组,寻找有没有值与差值相同。如果找到,返回两个元素的下标。
let twoSum = function(nums, target) { for (let i = 0; i < nums.length; i++) { let d_value = target - nums[i]; for (let j = i + 1; j < nums.length; j++) { if(nums[j] === d_value) return [i,j]; } }};console.log(twoSum([1,2,3,4,5],8))
运行结果:
二、数组法 时间复杂度:O(n)
思路:使用一层循环遍历整个数组,首先计算当前元素与target的差值d_value ,然后以d_value 为下标到数组result中寻找。如果有值,返回下标;如果没有找到,将当前元素存入result中(存入下标和值均为d_value)。
在这个方法中,最终的result数组中,有很多空元素位置。只有以nums数组中的元素为下标的地方有值,且值为nums数组中的元素本身。
let twoSum = function(nums, target) { let result = []; for(let i=0;i
运行结果:
三、ES6 新语法,Map 时间复杂度:O(n)
一个Map类似于一个对象,但相对于对象更加强大,其键可以是多种类型
通过map可以更加方便的设置、获取、比较值
let twoSum = (nums, target) => { let targetMap = new Map(); for (let i = 0; i < nums.length; i++) { const key = target - nums[i]; if (targetMap.has(key)) { return [targetMap.get(key), i] } targetMap.set(nums[i], i) }};console.log(twoSum([13,26,4,14,24],28));
运行结果:
转载地址:https://kaisarh.blog.csdn.net/article/details/105339287 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月28日 11时48分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
20200426 前端日报:ECMAScript 2020 的新功能速成
2019-05-01
面试中常考的字符串操作方法大全,包含ES6
2019-05-01
Vue.js 专栏课程推荐,助你更好迎接Vue 3.0
2019-05-01
尤小右:VitePress 初步实现小目标,极简静态站点生成器
2019-05-01
如何关注尤雨溪和 Vue.js
2019-05-01
CSS 中calc()的完整指南(一)
2019-05-01
Vue 3中令人激动的新功能:Fragment+Suspense+多v-model
2019-05-01
浅析Vuex及相关面试题答案
2019-05-01
Vue 3.0 中令人激动的新功能:Portals+新的自定义指令API
2019-05-01
requestAnimationFrame详解以及无线页面优化
2019-05-01
10个我必备的 VS code 拓展
2019-05-01
20200528 前端开发日报
2019-05-01
赠书 | 一文带你了解某搜索网站的优化
2019-05-01
20200508 前端开发周报:前端面试必备技巧
2019-05-01
JavaScript中的这些骚操作,你都知道吗?
2019-05-01
也许这才是你想要的微前端方案
2019-05-01
前端常用的60多种JavaScript工具方法
2019-05-01
一次性讲明白vue插槽slot
2019-05-01
谷歌博客:彻底弄懂JavaScript Promise
2019-05-01
javascript代码重构之:写好函数
2019-05-01