面试题41 和为S的连续正数序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

 1 class Solution {
 2 public:
 3     vector<vector<int> > v;
 4     vector<int> vc;
 5 
 6     vector<vector<int> > FindContinuousSequence(int sum) {
 7         if (sum <= 1)
 8             return v;
 9         int csum = 0, i = 0;
10         while (i <= sum / 2 + 2) {
11             vector<int>::iterator iter = vc.begin();
12             if (csum > sum) {
13                 csum -= vc[0];
14                 vc.erase(iter);
15             }
16             else if (csum == sum) {
17                 if (vc.size() > 1){
18                     v.push_back(vc);
19                 }
20                 i++;
21                 csum += i;
22                 vc.push_back(i);
23             }
24             else {
25                 i++;
26                 csum += i;
27                 vc.push_back(i);
28             }
29         }
30         return v;
31     }
32 };

题目描述

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

输出描述:

对应每个测试案例，输出两个数，小的先输出。

 1 class Solution {
 2 public:
 3     vector<int> v;
 4     vector<int> FindNumbersWithSum(vector<int> array,int sum) {
 5         if (array.size() <= 1)
 6             return v;
 7         int i = 0, j = array.size() - 1;
 8         while (i < j){
 9             if (array[i] + array[j] == sum){
10                 if (v.size() == 0){
11                     v.push_back(array[i]);
12                     v.push_back(array[j]);
13                 }
14                 else{
15                     if (v[0] * v[1] > array[i] * array[j]){
16                         v[0] = array[i];
17                         v[1] = array[j];
18                     }
19                 }
20                 i++;
21             }
22             else if (array[i] + array[j] < sum)
23                 i++;
24             else
25                 j--;
26         }
27         return v;
28     }
29 };