/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
/**
* 解法一:双层循环(不可用,运行超时)
* 思路:详情看以下代码
* 时间复杂度:O(n^2),双层循环
* 空间复杂度:O(1)
* 注意:如果这里的 nums 是有序的话,优化嵌套循环,可以考虑 “双指针”
*/
// export function twoSum(numbers: number[], target: number): number[] {
// const res: number[] = []
// const len = numbers.length
// if (len === 0) return res
// for (let i = 0; i < len - 1; i++) {
// const n1 = numbers[i]
// let flag = false // 是否得到结果
// for (let j = i + 1; j < len; j++) {
// const n2 = numbers[j]
// if (n1 + n2 === target) {
// res.push(i + 1)
// res.push(j + 1)
// flag = true
// break
// }
// }
// if (flag) break
// }
// return res
// }
/**
* 解法二:哈希
* 思路:遍历的同时借助哈希表,记录值和下标
* 时间复杂度:O(n),最多遍历数组一遍,每次查询哈希表都是O(1)
* 空间复杂度:O(n),最坏情况下找到数组结尾才找到,其他都加入哈希表,哈希表最长 n - 1
*/
export function twoSum(numbers: number[], target: number): number[] {
const res: number[] = []
const len = numbers.length
if (len === 0) return res
const map = new Map()
for (let i = 0; i < len; i++) {
const temp = target - numbers[i]
if (!map.has(temp)) {
map.set(numbers[i], i)
} else {
res.push(map.get(temp) + 1)
res.push(i + 1)
return res
}
}
return res
};
一站式解决前端面试高频算法题