最近开始在 LeetCode 网站上刷题,准备练练脑子。因为经常不动脑,感觉快生锈了。这个是第一题,比较简单。所有的解题代码都放在 Github 上。
问题描述:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题目描述的很清楚了,就是要从整数列表里面找出符合需求的两个数字,他们之和等于给定的目标值。输入是整数列表,输出是两个数字下标的列表。从给的例子上看,我们可以假设返回的列表,下标小的放在前面,比如是 [0, 1]
而不是 [1, 0]
。那假如没有找到符合要求的数字呢,应该返回什么呢?题目里面没有明确说明,我自己觉得这里应该返回一个空值。
思路一
首先,我们可以想到一种最简单的方法,就是遍历所有组合,这种方法比较暴力也很有效。下面的代码用 go 语言编写:
func twoSum(nums []int, target int) []int { n := len(nums) if n < 2 { return nil } for i := 0; i < n-1; i++ { for j := i + 1; j < n; j++ { if nums[i]+nums[j] == target { return []int{i, j} } } } return nil }
这个方法没什么好解释的,它的时间复杂度是O(n^2)
。
思路二
如果我们要降低时间复杂度,就必须减少迭代的次数。可以想到的一个优化思路是,针对数组进行排序,然后定义两个指针,分别从头和尾两个方向逼近,看起来有点像快速排序。如果指针指向的两个数之和大于目标值,则右边的指针左移。反之,左边的指针右移。直到找到符合需求的两个数。因为排序的最佳时间复杂度可以达到O(nlogn)
,接下来只遍历一次,时间复杂度是O(n)
,所以总的时间复杂度为 O(nlogn)。
这是一个不错的思路,但是这道题目要返回数字的下标,但是如果我们先排序会导致顺序就和初始状态不一样,所以还得想办法记录,所以这个思路最终实现也挺别扭的,就放弃了。
思路三
回到题目,我们要求出 a+b=target
,反过来看,如果我们当前遍历的数字是 a,也就是我们要看 target - a 这个结果在数组里面是否存在。为了加快查找的效率,我们可以用额外的空间换时间效率,哈希表是一个很好的策略。在遍历的时候我们把每个数字和它对应的坐标保存到一个哈希表中。相应的代码如下:
func twoSum(nums []int, target int) []int { tbl := make(map[int]int, len(nums)) for i, v := range nums { if j, ok := tbl[target-v]; ok { return []int{j, i} } tbl[v] = i } return nil }
肯定有符合条件的解啊,题目里说了
@匿名用户:谢谢指出,你说得对的。