# 数之和
# 两数之和
给i顶一个整数数组 nums 和一个目标值 target ,请你在该数组中找出为目标值的那两个整数,并返回他们的下标
你可以假设没中输入只会对应一个答案,但是,不能重复利用这个数组中同样的元素。
TIP
给定 nums = [2, 7, 11, 15] target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1];
# 解题思路
- 利用 Map 存储与已遍历元素的差值, has 方法判断元素是否为已遍历某个元素存储的差值;
- 从第一个元素开始遍历;
- 获取目标值与 nums[i] 的差值,即 k = target - nums[i],判断差值k 在 map中是否存在;
- 不存在, 则加入map,nums[i] 为 key,i为value,
- 存在,则返回下标 map.get(k)和i
- 遍历结束,返回nums。
时间复杂度O(n)
# 代码
const algorithm1 = (nums: number[], target: number) => {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
const k = target - nums[i];
if (map.has(k)) {
return [map.get(k), i];
}
map.set(nums[i], i);
}
return [];
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 三数之和
给定一个包含n个整数的数组 nums, 判断 nums 中是否存在三个元素 a, b, c, 使得 a + b + c = 0?请找出所有的满足条件且不重复的三元数组。
# 三元组不能重复
TIP
nums = [-1, 0, 1, 2, -1, -1];
结果: [[-1, 0, 1], [-1, -1, 2]]
const algorithm2 = (nums: number[], target: number) => {
const result = [];
let map = new Map();
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length; j++) {
const innerK = target - nums[i] - nums[j];
if (map.has(innerK)) {
result.push([i, map.get(innerK), j]);
break;
}
map.set(nums[j], j);
}
map.clear();
}
return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 没有重复元素
const algorithm2 = (nums: number[], target: number) => {
const result = [];
const set = new Set();
for (let i = 0; i < nums.length; i++) {
const k = target - nums[i];
let map = new Map();
for (let j = i + 1; j < nums.length && i < nums.length - 2; j++) {
const innerK = k - nums[j];
if (map.has(innerK) && !(set.has(i) || set.has(j))) {
result.push([i, map.get(innerK), j]);
set.add(i);
set.add(map.get(innerK));
set.add(j);
break;
}
map.set(nums[j], j);
}
}
return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21