和为S的两个数、和为S的连续正数序列

题1：和为S的两个数

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

解法1：双层循环，从前向后扫描，简单好想，时间复杂度为O(n^2)

//时间复杂度为O（n^2） vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> vec; if( array.empty() || array.size() <2) return vec; int length = array.size(); for(int i = 0 ;i<length;++i) { for(int j = i+1;j<length;++j) { if(array[i]+array[j] == sum) { vec.push_back(array[i]); vec.push_back(array[j]); return vec; } } } return vec; }

解法2：时间复杂度为O(n)的算法

思路：在数组中选择两个数，如果两个数之和等于S，就是要找的。如果小于S，希望两数之和再大一点，由于数组是递增排序的，可以选择两个数中较小的数后面的数，因为后面的数更大一些。如果大于S，我们想要数字之和小一点，可以选择较大数之前的数，因为前面的数小一点。根据此思路，可以定义两个指针，一个指向最前，向后找；另一个指向最后，向前找。

vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> vec; if( array.empty() || array.size() <2) return vec; vector<int>::iterator begin = array.begin(); vector<int>::iterator end = array.end(); --end; while(begin < end) { if(*begin + *end == sum) { vec.push_back(*begin); vec.push_back(*end); break; } else if(*begin + *end > sum) --end; else ++begin; } return vec; }

由于数组是排序的，所以较小数字一定位于较大数字之前，这就是while循环继续的条件。函数代码中只有一个while循环，从两端向中间进行扫描，所以时间复杂度为O(n)。

要求两数乘积最小，两种解法第一次找的的两个数字必然是乘积最小的，可以进行简单验证。

题2：和为S的连续正数序列

输入一个正数S，打印所有和为S的连续正数序列，至少含有两个数，例如，输入15，由于1+2+3+4+5 = 4+5+6 = 7+8 =15，所以打印三个序列，1~5,4~6,7~8.

思路：根据上面题目的想法，可以定义两个变量small,big,small初始化为1,big初始化为2.small增加到（1+S）/2，结束。

假设我们以求和为9为例，初始化两个变量后，此时介于small和big之间的序列为{1,2}，和为3。小于9，则接下来增加big的值big=3，序列为{1,2,3}，和为6，仍小于9，则继续增加big的值big=4，此时序列为{1,2,3,4}，和为10，此时大于9，我们就要删掉一些数字，于是我们增加small的值small=2，序列变为{2,3,4}，和为9，此时我们找到了第一组序列。

接下来我们再增加big的值big=5，序列变为{2,3,4,5}，和为14，大于9，则增加small的值small=3，序列变为{3,4,5}，和为12，大于9，则增加small的值small=4，序列变为{4,5}，和为9，这是第二组序列。

接下来我们增加big的值big=6，序列变为{4,5,6}，和为15，大于9，则增加small的值small=5，此时small=5 >= （1+S）/2=5,结束。

vector<int> InsertData(int start,int end) { vector<int> vec; for(int i = start;i<=end;++i) { vec.push_back(i); } return vec; } vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int>> res; if(sum <3) return res; vector<int> vec; int middle = (sum+1)/2; int small = 1; int big =2; int cursum = small + big; while(small < middle) { if(cursum == sum) { vec = InsertData(small,big); res.push_back(vec); } while(cursum > sum && small < middle) { cursum -= small; ++small; if(cursum == sum) { vec = InsertData(small,big); res.push_back(vec); } } ++big; cursum += big; } return res; }