问题：剑指 Offer 57. 和为s的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
思路：
使用双指针，分别指向第一个元素和最后一个元素，计算两个指针的内容之和，
如果大于目标值，则后面的指针向前移动，
如果小于目标值，则前面的指针向后移动，
如果等于目标值，则返回
如果两个指针相遇，则返回空值
分析：
最上面一行是数组，1,3,6,10,13,18,21,25,31,34,39,44,50.（总共13个数）
求的目标值是和为38，那么12+11+10+9+8+7+6+5+4+3+2+1种组合方法（都是小的数在前，大的数在后）
（黄色的表示指针）
首先，两个指针分别指向1和50,
既然1+50=51>38，
1是最小的数，加上50都比目标数大，那么其他数加上50也肯定比目标数大
所以可以删除（*）+50的所有情况；
如下表
（蓝色表示目前要删除的组合）
删除后我们可以发现这个问题里就没有50这个数字什么事了，不可能有哪个数和50相加会得到目标数
所以这个问题就变成了了在数组1,3,6,10,13,18,21,25,31,34,39,44（总共12个数）中求和为38的两个数
此时可以继续让两个指针分别指向最小的数1和最小的数44；
然后相加可知1+44=45>38，又可以分析
1是最小的数，加上44都比目标数大，那么其他数加上44也肯定比目标数大
所以可以删除（*）+44的所有情况；
如下表
（红色代表已经删除的数和组合，蓝色代表现在要删除的组合，黄色代表指针）
同理可知接下来1+39=40>38
删除所有（*）+39的组合
接下来
可以看到最小的数1，最大的数是34，
1+34=35<38，此时34是最大的数，1加上最大的数都比目标数小
那么1加上其他数肯定也比目标数小
那么可以删除1+（*）的所有情况
如下表
同理可知，接下来是3+34<38
删除所有3+（*）组合
6+34>38
删除（*）+34的组合
6+31<38
删除6+（*）的组合
10+31>38
删除（*）+31的组合
10+25<38
删除10+（*）的组合
最后指针停在13和25上，相加发现等于38，查找成功，返回
代码：
class Solution { public int[] twoSum(int[] nums, int target) { int i = 0, j = nums.length - 1; while(i < j) { int s = nums[i] + nums[j]; if(s < target) i++; else if(s > target) j--; else return new int[] { nums[i], nums[j] }; } return new int[0]; } }
总结：
为什么用双指针不会丢失解：
正如表中所示，表中所列举的组合是用穷举的方式得到的，没有漏掉的组合；
而删的时候也很稳，
如果当前两指针的和小于目标数，则删掉更小的数，
如果当前两指针的和大于目标数，则删掉更大的数。
其实两个指针的和就像是一个及格线，删掉不合格的组合
为什么两个指针要从首尾向中间移动：
其实不这样也可以，两个指针的和只是作为一个判断的标志
其实也可以随机获得两个数，比如10和31
发现10+31>38
那么可以删除所有10+（大于31）的组合
还可以删除（大于10）+31的组合
如下表
再随机取一对
6+34>38
可以删除所有6+（大于34）的组合
还可以删除（大于6）+34的组合
可以看到这两次重复删了10+34这对组合
而且这样不方便用代码删除组合，
而如果指针位于两头，则正好删除一行或者一列
只需 i + + 或 j - - 就行了，非常方便