求和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
1
2
3
4
| 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
|
解法一: 双层循环
1
2
3
4
5
6
7
8
9
10
11
12
13
|
const twoSum = (arr,target) => {
for (let i = 0; i < arr.length; i++) {
const parent = arr[i];
for (let j = 0; j < arr.length; j++) {
const child = arr[j];
if(parent + child === target) {
return [i,j];
}
}
}
}
|
解法二: 缓存, 空间换时间
1
2
3
4
5
6
7
8
9
10
11
12
| const twoSum = (arr,target) => {
const map = new Map();
for (let i = 0; i < arr.length; i++) {
const item = target - arr[i];
const key = map.get(item);
console.log(map);
if(key !== undefined) {
return [key, i]
}
map.set(arr[i],i);
}
}
|
合并两个有序数组
假设两个数组都是升序
[ 2, 4, 6, 7, 8, 12, 45, 0, 0 ] 7 nums1
[1, 4, 5, 6, 8, 14, 45] 7 nums2
已知 两个数组都是升序排列, 所以 数组的最后一个元素都是当前数组最大的;
nums1[0]