寻找和为定值的两个数

不忘初心，砥砺前行
 

作者 | 陌无崖
转载请联系授权 
输入一个整数数组和一个整数，在数组中查找一对数，满足他们的和正好是输入的那个整数，如果有多对数的和等于输入的整数，则全部输出，要求输出的结果中不应该出现重复，如输出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

END