和为S的两个数字

描述

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: 0 < len(array) < 10^5 ， 1 < array[i] < 10^6

1、解题思路1

        我自己想到的解题思路是先使用二分查找找出sum应该在数组中的位置，然后利用双指针遍历子数组，最终找出符合条件的两个数。具体算法实现请查看上一篇关于二分查找引起堆栈异常的总结。

2、解题思路2

        这是网上大神的写法，的确牛逼！！具体如下：

知识点：哈希表

        哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在O(1)时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

        我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表快速检验某个元素是否出现过这一功能。

具体做法：

• step 1：构建一个哈希表，其中key值为遍历数组过程中出现过的值，value值为其相应的下标，因为我们最终要返回的是下标。
• step 2：遍历数组每个元素，如果目标值减去该元素的结果在哈希表中存在，说明我们先前遍历的时候它出现过，根据记录的下标，就可以得到结果。
• step 3：如果相减后的结果没有在哈希表中，说明先前遍历的元素中没有它对应的另一个值，那我们将它加入哈希表，等待后续它匹配的那个值出现即可。

  import java.util.*;
  public class Solution {
      public ArrayList FindNumbersWithSum(int [] array,int sum) {
          ArrayList res = new ArrayList();
          //创建哈希表,两元组分别表示值、下标
          HashMap mp = new HashMap();
          //在哈希表中查找target-numbers[i]
          for(int i = 0; i < array.length; i++){
              int temp = sum - array[i];
              //若是没找到，将此信息计入哈希表
              if(!mp.containsKey(temp)){ 
                  mp.put(array[i], i);
              }
              else{
                  //取出数字添加
                  res.add(temp);   
                  res.add(array[i]);
                  break;
              }
          }
          return res;
      }
  }