描述
Category：algorithms
Difficulty：Easy
Tags：array | hash-table
Companies：adobe | airbnb | amazon | apple | bloomberg | dropbox | facebook | linkedin | microsoft | uber | yahoo | yelp
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
代码
自己的实现方式：暴力法直接遍历
/* * @lc app=leetcode.cn id=1 lang=javascript * * [1] 两数之和 */ // @lc code=start /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for(var i = 0; i < nums.length; i++) { var tempNum = target - nums[i]; for(var j = i + 1; j < nums.length; j++) { if ( nums[j] === tempNum) { return [i, j]; } } } }; console.log(twoSum([2, 7, 11, 15], 9)); // @lc code=end
测试提交
提交记录
执行用时
Using ES6 data structure Map. Time complexity is O(n).
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let map = new Map(); for(let i = 0; i < nums.length; i ++) { if(map.has(target - nums[i])) { return [map.get(target - nums[i]), i]; } else { map.set(nums[i], i); } } return []; };
Using Object. Time complexity is also O(n).
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let hash = {}; for(let i = 0; i < nums.length; i++) { const n = nums[i]; if(hash[target - n] !== undefined) { return [hash[target - n], i]; } hash[n] = i; } return []; }
对比结果很明显，不得不说一个题目就能暴露自己的很多问题，自己存在的短板，思考问题的角度。
要点学习
array
hash-table：哈希表也被称为散列表，是一种特殊的数据结构，它同数组、栈、链表等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。
算法复杂度：是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。
