面試中常被問及的一道面試題,其實這道題不難,關鍵是寫出來的算法需要在時間復雜度上盡量做到最優。實現不難,但是要做到讓面試官滿意那就得多多思考。
# 方法1: 循環+indexOf
## 思路
循環數組,使用目標值減去當前循環的元素,帶著計算出的減后的值去數組中尋找有沒有這個值,如果有即indexOf不是-1,那當前循環的索引和indexOf返回的索引,即為答案
## 實現
```
function findIndexes1 (arr, target) {
let currentNum, otherNum, currentIndex, otherIndex
for (let i = 0, len = arr.length; i < len; i++) {
currentNum = arr[i]
// 當前元素如果大于目標值,則直接進行下一輪循環,加快檢索速度
if (currentNum > target) {
continue
}
otherNum = target - currentNum
otherIndex = arr.indexOf(otherNum)
if (otherIndex !== -1) {
currentIndex = i
break
}
}
return [currentIndex, otherIndex]
}
```
## 說明
這個算法看似只有一個循環,實則不然。因為循環內部使用了indexOf方法,而這個方法底層仍然是靠循環實現的,所以時間復雜度仍然是 On平方
# 方法2 循環+Map
## 思路
思路和方法1其實特別像。只不過是把使用indexOf()在數組中尋找的方法替換為使用Map的has()在Map中尋找的方法。消除了嵌套循環,從而性能得到提升。具體做法是:先將數組轉為Map,其中key為數組中的數值,value為數值的下標索引。然后循環數組,計算出另一個值,使用has()尋找是否有這個值,若找到,使用get()獲取索引,跳出循環;若沒找到,繼續下輪循環。
## 實現
```
function findIndexes2 (arr, target) {
let map = new Map()
// 數組轉Map key為數值 value為下表索引
arr.forEach((item, index) => {
map.set(item, index)
})
let currentIndex, otherIndex, currentNum, otherNum
for (let i = 0, len = arr.length; i < len; i++) {
currentNum = arr[i]
if (currentNum > target) {
continue
}
otherNum = target - currentNum
if (map.has(otherNum)) {
currentIndex = i
otherIndex = map.get(otherNum)
break
}
}
return [currentIndex, otherIndex]
}
```
# 綜合性能測試
生成一個測試數組,這個數組共有100002個元素,其中前100000個元素均為1,最后兩個元素分別是2和3。目標值設計的是5。這樣做的目的是程序需要循環好多次才能找到結果,從而對比出性能的差異。
```
function getArr () {
let arr = []
let i = 0
while (i < 100000) {
arr.push(1)
i++
}
arr.push(2, 3)
return arr
}
```
```
let start = Date.now()
console.log(findIndexes1(getArr(), 5))
let end = Date.now()
console.log(end - start) // chrome 5753ms
```
```
let start = Date.now()
console.log(findIndexes2(getArr(), 5))
let end = Date.now()
console.log(end - start) // chrome 35ms
```
結果不言而喻,一個四位數,一個兩位數,這性能差異完全不在一個數量級。