＂數據結構與算法之字典
兩數之和
https://leetcode.cn/problems/two-sum/
描述
給定一個整數數組nums和一個整數目標值target，請你在該數組中找出和為目標值target的那兩個整數，并返回它們的數組下標
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現
你可以按任意順序返回答案
示例 1
輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2
輸入：nums = [3,2,4], target = 6 輸出：[1,2]
示例 3
輸入：nums = [3,3], target = 6 輸出：[0,1]
提示
2 <= nums.length <= 1 0 4 10^4 104
- 1 0 9 10^9 109 <= nums[i] <= 1 0 9 10^9 109
- 1 0 9 10^9 109 <= target <= 1 0 9 10^9 109
只會存在一個有效答案
進階：你可以想出一個時間復雜度小于O( n 2 n^2 n2) 的算法嗎？
算法實現
1 ）使用Map來匹配
function twoSum(nums: number[], target: number): number[] {const map = new Map();for (let i = 0; i < nums.length; i ++) {const current = nums[i];const wanted = target - current;if (map.has(wanted)) {return [map.get(wanted), i]}map.set(current, i);} };
這種算法的思想就是基于一個注冊表來查詢匹配，返回匹配上的結果
2 ）暴力枚舉
function twoSum(nums: number[], target: number): number[] {const n = nums.length;for (let i = 0; i < n-1; i++) {for (let j = i + 1; j < n; j++) {if (nums[i] + nums[j] === target) {return [i, j];}}}return [undefined, undefined]; }
注意，這里使用雙指針，將所有可能得結果進行遍歷，如果匹配則返回相對索引
還有就是遍歷的邊界問題如果 i < n, j < n 也是可以的，越界后，無非就是數值 + undefined, 結果是NaN，這得益于javascript的弱類型語言
如果是其他強類型語言，就會報錯，所以，需要特別注意下邊界的問題
"
