LeetCode - 两数之和

给定一个整数数组 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]

1. 分析

两数之和，入参是一个数组(nums)，以及目标值(target)。

要求输出对应的索引值/下标(index)

对应的类型:

function twoSum(nums: number[], target: number): number[] {

}

解题分析：

我们需要一个数据结构，它是一个映射关系，存储当前的索引和当前的值。

遍历这个数组，找出当前的值和目标值的差值，判断是否在这个映射关系里面。

如果有，代表这两个数相加为总和，直接输出对应索引。

如果否，证明不满足，加一组映射关系。

代码:

function twoSum(nums: number[], target: number): number[] {
  const map: Map<number, number> = new Map();
  for (let index = 0; index < nums.length; index++) {
    const diff = target - nums[index];
    if (map.has(diff)) {
      return [map.get(diff)!, index];
    }
    map.set(nums[index], index);
  }
  return [];
}

const res1 = twoSum([1, 2, 4, 5], 10);
console.log("res1>>", res1); // []

const res2 = twoSum([1, 2, 4, 5], 7);
console.log("res2>>", res2); // [1,3]

LeetCode - 两数之和

Table of contents

1. 分析