寻找和为定值的两个数

作者 | 陌无崖

转载请联系授权

题目要求

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