每日一题《剑指offer》数组篇之和为S的两个数字
今日题目链接:和为S的两个数字
和为S的两个数字
难度：中等
描述
输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
数据范围
数据范围: 0≤len(array)≤105， 1≤array[i]≤106
举例
解题思路
方法一：哈希表；我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表快速检验某个元素是否出现过这一功能。
方法二：双指针；这道题目还有一个条件是数组是升序序列，在方法一中没有用到。这个条件有什么用？既然数组是有序的，那我们肯定知道和找到一定程度就不找了，我们为什么要从最小的两个数开始相加呢？我们可以用二分法的思路，从中间开始找。
使用双指针指向数组第一个元素和最后一个元素，然后双指针对撞移动，如果两个指针下的和正好等于目标值sum，那我们肯定找到了，如果和小于sum，说明我们需要找到更大的，那只能增加左边的元素，如果和大于sum，说明我们需要找更小的，只能减小右边的元素。
实现代码（java）
方法一：
import java.util.*; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<Integer>(); //创建哈希表,两元组分别表示值、下标 HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); //在哈希表中查找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; } }
方法二:
import java.util.*; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<Integer>(); //左右双指针 int left = 0, right = array.length - 1; //对撞双指针 while(left < right){ //相加等于sum，找到目标 if(array[left] + array[right] == sum){ res.add(array[left]); res.add(array[right]); break; //和太大，缩小右边 }else if(array[left] + array[right] > sum) right--; //和太小，扩大左边 else left++; } return res; } }
