LeetCode-1.两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例 1：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法一之暴力破解
直接暴力破解，双层循环，两数相加判断。
分别拿两次循环的数字，判断是不是目标值，并且判断不是同一个元素。
代码实现
我们看到嵌套循环，应该立马就可以得出这个算法的时间复杂度为 O(n2)。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
// 双层循环，两数相加判断 && 判断不是同一个元素
if (nums[i] + nums[j] === target && i != j) {
return [i, j];
}
}
}
};
// ===================================================================
// ========================== @test ==================================
// ===================================================================
console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(twoSum([2, 7, 2, 4], 4)); // [ 0, 2 ]
解法二之对象记录
使用对象记录当前元素的目标值和当前索引，下次再循环如果对象中包含此值，那么此值就是目标值
- 每当循环一个数的时候，我们可以知道需要的目标值是几
（target - num = 目标值）。 - 如果没找到，就把目标值当成
key，当前索引当成value，存进对象里。 - 那么下次循环的时候，当前值在对象里，那么就找到了目标值取出索引与当前索引一起返回。
代码实现
这次只循环了一次，时间复杂度 O(n)，空间复杂度 O(n)，典型用空间换时间。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let obj = {};
for (let i = 0; i < nums.length; i++) {
let num = nums[i];
// 如果当前值在对象，取出索引。
if (num in obj) {
return [obj[num], i];
}
// 如果没找到，就把目标值当成 key，当前索引当成 value，存进对象里。
// 如果此次循环是 2, 那么我的目标值就是 7 索引是 1。
obj[target - num] = i;
}
};
// ===================================================================
// ========================== @test ==================================
// ===================================================================
console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]
console.log(twoSum([2, 7, 2, 4], 4)); // [ 0, 2 ]