# 1. 两数之和
# 题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
# 题解
# 暴力法
双重循环遍历所有情况判断是否等于 target
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length - 1; ++i) {
for (let j = i + 1; j < nums.length; ++j) {
let t = nums[i] + nums[j];
if (t === target) return [i, j];
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
空间复杂度：O(1)
时间复杂度：O(n²)
# 哈希表
遍历数组，用哈希表保存
key: 目标值 - 当前值
value: 当前值的索引
1
2
2
遍历的同时查看哈希表如果当前值存在 key 中返回结果
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let m=new Map();
for(let i=0;i<nums.length;i++){
if(m.get(target-nums[i])>=0){
return [m.get(target-nums[i]),i];
}else{
m.set(nums[i],i);
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
时间复杂度： O(n)
空间复杂度： O(n)