Two Sum
•--
Find two numbers that add up to target using Hash Map - O(n) time complexity
Find two numbers in an array that add up to a target value
問題描述
給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，並返回它們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。
你可以按任意順序返回答案。
範例
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1]
限制條件
2 <= nums.length <= 10⁴-10⁹ <= nums[i] <= 10⁹-10⁹ <= target <= 10⁹- 只會存在一個有效答案
解題思路
Hash Map 解法 O(n) 使用 Hash Map
儲存已遍歷過的元素及其索引，查找目標元素的補數
解決方案
typescript
export function twoSum(nums: number[], target: number): number[] {
const map = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
map.set(nums[i], i);
}
return [];
}