值得紀念的leetcode第一題 —— 兩數之和，其不僅考驗對陣列的基本操作，也能夠學會使用資料結構來優化演算法效率。
題目說明
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。
你可以假設每個輸入只會對應一個答案，而且你不能使用兩次相同的元素。
你可以按任意順序返回答案。
解題思路
透過雙層迴圈即可透過遍歷的方式找出答案。然而，此暴力解法的時間複雜度為O(n2)。
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 [] // 沒找到符合條件的結果
};
更快的解法 —— 哈希表
什麼是哈希表?
- 哈希表（hash table），又稱作雜湊表，其透過建立鍵
key與值value之間的映射，來實現高效率的元素查詢。具體地，我們向哈希表中輸入一個鍵key，則可以在O(1)時間內獲取對應的值value。 - 邏輯：
- 使用一個 Map（哈希表）來記錄已經看過的數字和對應的索引。
- 在每次迴圈時，先計算出「差值」complement = target - nums[i]。
- 檢查這個差值是否已經存在於哈希表中：如果存在，表示找到了答案。
- 如果還沒存在，就把目前的數字及其索引記錄到哈希表中。
var twoSum = function(nums, target) {
// 建立一個空的哈希表
const map = new Map();
for(let i = 0; i < nums.length; i++){
const complement = target - nums[i];
// 查找 complement 是否已存在於 map 中
if(map.has(complement)){
// 找到答案了!
return [map.get(complement), i];
}
// 如果還沒找到符合的組合，就把當前數字 nums[i] 及其索引 i 存進 map 中。
map.set(nums[i], i);
}
return []; // 沒找到符合條件的結果
};
- 哈希表解法的優點：
- 只需要遍歷一次陣列，使得時間複雜度降為 O(n)
- 使用空間換時間，額外使用了一個哈希表來記錄已遍歷過的元素及其索引
總結
透過暴力解法，可以以時間複雜度O(n2)得出答案，而透過哈希表，由於可以根據哈希表記錄先前查詢的結果並進行查找，只需要遍歷一次陣列，使得時間複雜度降為 O(n)。
本題雖然簡單，但蘊含了資料結構與演算法的思維轉變，從暴力枚舉到使用哈希表，體現了空間換時間的設計哲學，非常的beautiful。
