# 两数之和
来源: https://leetcode.cn/problems/two-sum/ (opens new window)
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3
2
3
输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2
2
解题思路:
关键点在于交换律思路
点击查看代码
/**
* 两数之和
* @param {number[]} nums
* @param {number} target
* @returns number[]
*
* 双循环
* 时间复杂度 O(n**2)
* 空间复杂度 O(1)
*
* map映射
* 时间复杂度 O(n)
* 空间复杂度 O(n)
*/
const twoNum = (nums, target) => {
// 暴力解, 双循环
// for (let i = 0, len = nums.length; i < len; i++) {
// for (let j = i + 1; j < len; j++) {
// if (nums[i] + nums[j] === target) {
// return [i, j]
// }
// }
// }
// return []
// map 映射
const map = new Map()
for (let i = 0, len = nums.length; i < len; i++) {
const x = target - nums[i]
if (map.has(x)) {
return [map.get(x), i]
}
map.set(nums[i], i)
}
return []
}
const twoSum2 = (nums, target) => {
// if (nums.length === 0) return false
// const dict = Object.fromEntries(nums.map(n => [n, true]))
// return nums.some(n => dict[target - n])
// 2. 不考虑性能, 直接 some
return nums.some(n => nums.includes(target - n))
}
console.log(twoNum([3,2,4], 6))
console.log(twoSum2([1, 1], 2))
// [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# TS 版本
点击查看代码
const twoSumFunc = (
nums: number[],
target: number,
): boolean => {
// if (nums.length === 0) return false
// const dict = Object.fromEntries(nums.map(n => [n, true]))
// return nums.some(n => dict[target - n])
// 2. 不考虑性能, 直接 some
return nums.some(n => nums.includes(target - n))
}
const twoSum = (
nums: number[],
target: number,
set: Set<number> = new Set([])
): boolean => {
if (nums.length === 0) return false
const delta = target - nums[0]
return set.has(delta) ? true : twoSum(nums.slice(1), target, new Set([...set, nums[0]]))
}
type ToTuple<L extends number, T extends any[] = []> =
T extends { length: L } ? T : ToTuple<L, [...T, any]>
type Sub<A extends number, B extends number> =
ToTuple<A> extends [...ToTuple<B>, ...infer Tail] ? Tail['length'] : -1
type Tail<T> = T extends [any, ...infer Tail] ? Tail : []
type TTwoSum<N extends number[], T extends number, Set extends any = []> =
N['length'] extends 0
? never
: Set extends Sub<T, N[0]>
? true
: TTwoSum<Tail<N>, T, Set | N[0]>
type Expect<T extends true> = T
type Equal<X, Y> =
(<T>() => T extends X ? 1 : 2) extends
(<T>() => T extends Y ? 1 : 2)
? true
: false
type Cases = [
Expect<Equal<TTwoSum<[2, 7, 11, 15], 9>, true>>,
Expect<Equal<TTwoSum<[2, 7, 11, 15], 2>, never>>,
]
// [true, true]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48