寻找和为定值的两个数

不忘初心，砥砺前行  

作者 | 陌无崖

转载请联系授权 

输入一个整数数组和一个整数，在数组中查找一对数，满足他们的和正好是输入的那个整数，如果有多对数的和等于输入的整数，则全部输出，要求输出的结果中不应该出现重复，如输出1,4和4,1

在了解如何使用散列映射之前，首先我们需要了解什么是散列映射，千万不要被这个专业词汇给吓住，其实很简单。我们看看吧。

什么是散列  

Hash一般翻译成散列，或哈希，就是把任意长度的输入（又叫做预映射）通过散列算法，变换成固定程度的输出，该输出就是散列值。

什么是散列表

即哈希表，是根据键值（key）而直接进行访问的数据结构

为什么需要散列表

1. 对于数组来说寻址容易，但是插入和删除较为困难对于链表来说寻址困难，但是插入和删除容易，那么有没有一种数据结构可以结合数组和链表的优点呢？ 就是哈希表。

2. 无论哈希表中由多少数据，插入和删除其时间复杂度接近O(1)哈希表的操作非常快，一秒钟通常可以查找上千条记录。

解题思路

知道上面的定义，让我们来看看解题思路，首先我们需要明确的是哈希表在进行查询的时候，时间复杂度为O(1)。 对于上题，我们按照传统的思路设计我们会遍历数num的同时，来验证sum-num是否也在该数组中,这就需要用到我们的查询操作，如果是数组的查询，每遍历一个数的时候，做最坏的打算，之多遍历n此，因此n个数的遍历就是O(n^2),所以为了减少查询的时间复杂度，我们就可以利用哈希表来存储我们的原始数据。

代码思路

1. 首先我们需要一个散列表来存储数据，go语言中可以用map实现。

2. 然后我们可以遍历我们的原始数组，进行查询比较。 这里需要注意按照题目的要求已经遍历的不可以在进行遍历了，因此我们对已经遍历的需要进行标记。 结合map我们可以用key所对应的value值进行判定。

完整代码

// 解法一：散列映射

func SelectNum(data []int, sum int) [][]int {

// 构建一个空间为n的散列表即map,bool值用来标记是否已经被使用，下次不需要再进行使用

var m map[int]bool

m = make(map[int]bool, len(data))

// 定义一个存放结果的散列

var result [][]int

for i := 0; i < len(data); i++ {

m[data[i]] = false

}

// 循环遍历我们的数组

for i := 0; i < len(data); i++ {

if _, ok := m[sum-data[i]]; ok && m[data[i]] == false {

// 定义一个临时数组

temp := []int{data[i], sum - data[i]}

// append函数会自动扩充数组

result = append(result, temp)

m[sum-data[i]] = true

}

}

return result

}

对于上面的解法，虽然我们的时间复杂度得到了降低，但是由于我们使用了散列表，使得我们的空间复杂度升到了O(n),那么有没有一种方法可以让我们的空间复杂度降低到O(1)呢？

这就需要用到我下面分享的方法。

解题思路

我们都知道如果对我们的数组进行排序 ( 关于排序可以看我的这个文章 )， 我们有各种方法求解这个题，那么我们就按照一个已经排好序的数组进行分析，对于有序数组a[n],存在这样的性质，a[i] + a[i+n] <= a[i] + a[i+n+1],因此我们可以按照这样的性质通过比较a[i] + a[i+n]和sum进行不断的缩小范围。

代码思路

1. 为了缩小范围，我们可以定义首尾指针begin，end来控制范围。  

2. 对于数组data,如果data[begin] + data[end] > sum 则应该移动end指针。 如果data[begin] + data[end] < sum 则应该移动begin指针。

完整代码

// 解法二：排序夹逼

func SelectNum_Two(data []int, sum int) [][]int {

var result [][]int

// 先排序数组

Qiuck_Sort(data, 0, len(data)-1)

// 定义两个前后指针指向数组的首和尾

begin, end := 0, len(data)-1

for begin < end {

if data[begin]+data[end] > sum {

// 缩小范围

end--

} else if data[begin]+data[end] < sum {

begin++

} else {

temp := []int{data[begin], data[end]}

result = append(result, temp)

// 继续缩小范围进行寻找

begin++

end--

}

}

return result

}

END

查看完整源码可以点击阅读原文进入github仓库，如果喜欢，感谢你为我点一个星星^_^

END