有人相愛，有人夜里開車看海，我是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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/501206.html
標籤：其他