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⁹
只會存在一個有效答案

解題思路

### 暴力解法 O(n²) 對每個元素，遍歷數組的其餘部分來尋找它所對應的目標元素

### Hash Map 解法 O(n) 使用 Hash Map 儲存已遍歷過的元素及其索引，查找目標元素的補數

解決方案

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 [];
}

Command Palette