面試中常被問及的一道面試題，其實這道題不難，關鍵是寫出來的算法需要在時間復雜度上盡量做到最優。實現不難，但是要做到讓面試官滿意那就得多多思考。
# 方法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
```
結果不言而喻，一個四位數，一個兩位數，這性能差異完全不在一個數量級。
