网站首页 返回列表
像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之FindIndex

18-10-18 16:48:06 云丶先生 149

### 习题一：
给定一个整数数组，使其中两个数字相加得到特定目标而返回两个数字的索引。假设每个输入只有一个解决方案，并且不会两次使用相同的元素。
给定：`nums = [2, 7, 11, 15], target = 22`
由于：`nums[1] + nums[3] = 7 + 15 = 22`
输出：`[1, 3]`

### 解题思路：
首先由最笨的方法逐步转入利用巧妙的算法，尽量多培养自己逐渐升级思维的习惯，这样才可以深入理解各种算法带来的精髓。

### 方法一：蛮力
循环遍历每个元素x并找出是否有另一个值等于target-x
```go
func twoSum1(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[j] == target - nums[i] {
				return []int{i, j}
			}
		}
	}
	return []int{}
}
```
此方法看似简单，可实际遍历后的时间复杂度为：n²

### 方法二：two-pass map
为了提高效率，我们可以利用map保存元素和对应的索引，利用高效的map来单次遍历查询，时间复杂度可以减少为：n
```go
func twoSum2(nums []int, target int) []int {
	h_table := map[int]int{}
	for i := 0; i < len(nums); i++ {
		h_table[nums[i]] = i
	}
	for i := 0; i < len(nums); i++ {
		diff := target - nums[i]
		if _, ok := h_table[diff]; ok && h_table[diff] != i{
			return []int{i, h_table[diff]}
		}
	}
	return []int{}
}
```
可这里还是看起来很别扭，因为还是进行了2次遍历。

### 方法三：one-pass map
事实上，只需要1次就行了。当我们迭代并将元素插入表中时，我们还可以回顾检查表中是否已存在当前元素的补码。如果存在，我们找到了解决方案并立即返回。
```go
func twoSum3(nums []int, target int) []int {
	h_table := map[int]int{}
	for i := 0; i < len(nums); i++ {
		diff := target - nums[i]
		if _, ok := h_table[diff]; ok && h_table[diff] != i{
			return []int{h_table[diff], i}
		} else {
			h_table[nums[i]] = i
		}
	}
	return []int{}
}
```
最后看看3种方法的运行结果吧
```go
fmt.Println(twoSum1([]int{2,7,11,15}, 22))
fmt.Println(twoSum2([]int{2,7,11,15}, 22))
fmt.Println(twoSum3([]int{2,7,11,15}, 22))
```
输出：
```go
[1 3]
[1 3]
[1 3]
```
最后，还可以使用多一些的测试用例，测试一下3种方法运行时间的差别，即可深入理解算法带来的效率。

关键字词[算法]

分享到：

上一篇：CentOS7安装nginx服务

下一篇：leetcode基础算法学习之addTwoNumbers

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与