题目描述:
题目一:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,得它们的和正好是 s。如果有多对数字的和等于 s,输出任意一对即可。
题目二:输入一个正数 s,打印出所有和为 s 的连续正数序列(至少两个数)。
算法思想:
题目一:我们先在数组中选择两个数字,如果它们的和等于输入的 s,我们就找到了要找的两个数字。如果和小于 s 呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些,那么两个数字的和也要大一些, 就有可能等于输入的数字 s 了。同样, 当两个数字的和大于输入的数字的时候,我们可以选择较大数字前面的数字,因为排在数组前面的数字要小一些。
题目二:考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1,big 初始化为 2。如果从 small 到 big 的序列的和大于 s,我们可以从序列中去掉较小的值,也就是增大 small 的值。如果从 small 到 big 的序列的和小于 s,我们可以增大 big,让这个序列包含更多的数字。因为这个序列至少要有两个数字,我们一直增加 small 到(1+s)/2 为止。