题目一(和为 s 的两个数字)

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

算法思路

由于给定的数组是递增有序的，那么我们设置左右指针分别指向数组的首尾，然后从两端向中间夹逼。如果当前指针指向的两个数之和大于 S，那么说明右指针指向的数大了，应该后退一位；如果当前指针指向的两个数之和小于 S，那么说明左指针指向的数小了，应该前进一位。直到首次遇到两数之和恰好等于 S，即所求。由于数组递增有序，那么首次遇到的两数之积必然最小。

算法实现

题目二

如果题目一去掉递增有序呢？

算法思路

那么题目一的思路便失效了。
我们取可能的一对数分析，我们发现对于这对数 a,b，用 S 减去 a 所得的数字 b 其实也在原数组中，那么当 S 减去 b 时又得到了 a，也就是当他们都被减的时候，a 一定会重复出现。而非所求的数字不会有此情况。那么我们可以利用哈希表，以原数组的值为键，以 S 与数组元素的差值为值，构造哈希表。如果新的差值是哈希表中的键，那么就可以确定这对数(哈希表中的键和值)是候选解，记录下来。最后从候选解中选出乘积最小的那对即可。

算法实现

题目三(和为 s 的连续正数序列)

输入一个正数 s，打印出所有和为 s 的连续正数序列(至少含有两个数)。例如，输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以打印出 3 个连续序列 1~5、4~6 和 7~8。

算法思路

题目意思就是从 1~s 的正数序列中，找到可能的连续序列，其和为 s。那么正数序列仍然可看成递增排序的，借鉴于题目一，我们仍然设置左右指针，左指针仍然指向第一个正数，右指针指向末位正数？我们发现，左指针的活动范围显然一定不会超过 (1+s)/2。那么其实最简单的思路是左指针每确定一个位置，右指针就移动到可能的位置进行判断，然后下一次左指针移动一位，右指针就后退到可能的位置进行判断，依次类推，直到左指针走到边界。那么这样必然需要重复计算两指针范围内的数之和。
其实，我们可以将右指针指向第二个正数，从最小的范围开始判断连续序列之和是否为 s，然后右指针不断前进，并随时统计连续序列之和。如果连续序列大于 s，并且左指针在合法范围内，那么连续序列之和先减去左指针指向的数字，然后左指针前进。如果此时情况满足，那么立即打印。否则右指针继续前进判断。

算法实现

复杂度

题目的时间复杂度为均为 O(n)复杂度，除了题目二的空间复杂度为O(n)，其他均为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网