Skip to main content

0001-Two Sum

题目

两数之和

思路

暴力解法

使用两层遍历来遍历同一个数组,每层元素相加满足条件,则返回结果

求差法

只使用一层遍历,空间换时间:

  1. 定义一个 Map 来存储“数组元素:索引”数据
  2. 遍历时,如果目标值减去当前值的结果值,能在 Map 找到,则返回结果

代码

暴力解法:

function twoSum(nums: number[], target: number): number[] {
let res = []
// 第1层遍历
for (let i = 0; i < nums.length; i++) {
const a = nums[i]
// 第2层遍历
for (let j = 0; j < nums.length; j++) {
const b = nums[j]
// 符合条件时返回索引数组
if (a + b === target && i !== j) {
res = [i, j]
}
}
}
return res;
};

求差法:

function twoSum(nums: number[], target: number): number[] {
// 定义Map
const diffs = {}
const len = nums.length
// 第1层遍历
for (let i = 0; i < len; i ++) {
// 目标值-当前值,如果能结果能在Map检索到,则返回结果
if (diffs[target - nums[i]] !== undefined) {
return [diffs[target - nums[i]], i]
}
// 如果结果检索不到,则放入Map
diffs[nums[i]]=i
}
};