20190727算法题-两数之和

|

算法题

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题

方法一 双层for循环

我们用双层for循环，遍历每个元素el，找到是否有target-el的元素存在数组里，找到则输出索引。

1
2
3
4
5
6
7
8
9
function sum (nums, target) {
	for (let i = 0; i < nums.length; i++) {
		for (let j = 0; j < nums.length; j++) {
			if(nums[i] === target - nums[j] && i!==j) {
				return [i, j]
			}
		}
	}
}

这样的时间复杂度是 O(n^2)，空间复杂度为O(1)

很明显，这样的方法耗时太久，不好。

方法二 利用对象查找

因为在一个对象里找到是否有某个属性值，时间复杂度为O(1),所以我们可以第一次遍历数组，生成一个对象，然后第二次遍历，去找对象中是否有target-nums[i]的值，有的话返回。这样总的时间复杂度为O(n)，比第一种方法要好一些，只是需要一些内存去存储对象，空间复杂度为O(n),相当于拿空间换时间。

1
2
3
4
5
6
7
8
9
10
11
function sum (nums, target) {
	let obj = {};
	for (let i = 0; i < nums.length; i++) {
		obj[nums[i]] = i;
	}
	for (let i = 0; i < nums.length; i++) {
		if(obj[target - nums[i]] && i == obj[target - nums[i]]) {
			return [i, obj[target - nums[i]]]
		}
	}
}

方法三 优化第二种方法

上面我们执行了两次for循环，我们进行一下优化，在一次循环里解决。第一次循环将数组生成对象时就返回去检查对象里是否有符合target - nums[i]的属性值，有则返回。

1
2
3
4
5
6
7
8
9
function sum (nums, target) {
	let obj = {};
	for (let i = 0; i < nums.length; i++) {
		if(obj[target - nums[i]] >= 0) {
			return [obj[target - nums[i]], i]
		}
		obj[nums[i]] = i;
	}
}