LeetCode使用JavaScript破解兩數之和
有人相愛，有人夜裡開車看海，我是leetcode第一題都做不出來
題目
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重複出現。
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
方式一:暴力破解
第一眼看到這個問題時，想到的解題方法就是使用for循環，兩個for循環進行遍歷,每一項進行相加，當等於target時，就可以返回他們的下標
var twoSum = function(nums, target) {
for(let i=0;i<nums.length;i++){
for(let j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]===target){
return [i,j]
}
}
}
return []
};
這種方式屬於暴力破解，枚舉每一種可能性，雖然能解題但是耗費的性能比較大，時間複雜度：O(N^2)，其中 N是數組中的元素數量。最壞情況下數組中任意兩個數都要被匹配一次。
方式二：哈希
可以創建一個哈希表，對於每一個 x，我們首先查詢哈希表中是否存在 target - x，然後將 x 插入到哈希表中，即可保證不會讓 x 和自己匹配。
具體步驟如下：
- 第一步：創建一個map
- 第二步：for循環遍曆數組
- 第三步：用target減去每一項，計算哪個數能跟當前的數字相加得到target
- 第四步：檢查map里有沒有這個數，如果有則返回結果，如果沒有則把nums[i]當做key, i當做value放入到map里
var twoSum = function(nums, target) {
let map = new Map();
for(let i=0;i<nums.length;i++){
let resault = target - nums[i]
if(map.has(resault)){
return [map.get(resault),i]
}else{
map.set(nums[i],i)
}
}
return []
};
知識點
Map 對象保存鍵值對，並且能夠記住鍵的原始插入順序。任何數據類型都可以作為鍵或者值
Map的一些基本操作
// 創建一個map對象
const map = new Map()
// 添加鍵值
map.set('a',1)
// 刪除值
map.delete('a')
// 是否存在某一個鍵
map.has('a')
// 獲取map的長度（不用帶括號）
map.size
