面试题41：和为s的两个数字VS和为s的连续正数序列

题目一：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和为s，输出任意一对即可。

 1 vector<int> findNumberwWithSum(vector<int>&data, int sum)
 2 {
 3     int n = data.size();
 4     vector<int>result;
 5     if (n < 2)
 6         return result;
 7     int left = 0, right = n-1;
 8     while (left < right)
 9     {
10         if (data[left]+data[right] == sum)
11         {
12             result.push_back(data[left]);
13             result.push_back(data[right]);
14             break;
15         }
16         else if (data[left]+data[right] < sum)
17             ++left;
18         else
19             --right;
20     }
21     return result;
22 }

题目二：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5 = 4+5+6=7+8=15，所以结果打印出3个连续序列1~5、4~6、7~8.

分析：有了解决前面问题的经验，我们也考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2.如果从

small到big的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small的值。如果从small到big的序列的和小于s，我们可以增大

big，让这个序列包含更多的数字。因为这个序列至少要两个数字，我们一直增加small到(1+s)/2为止。

void findContinuousSequence (int sum)
 {
    if (sum < 3)
        return ;
     int small = 1;
     int big = 2;
     int middle = (1 + sum) /2;
     int curSum = small + big;
    while (small < middle)
     {
         if (curSum == sum)
         {
             for (int i = small; i <= big; ++i)
                 cout << i ;
             big++;
             curSum+=big;
         }
         else if (curSum > sum)
         {
             curSum-=small;
             small++;
         }
         else
         {
            big++;
            curSum+=big;
         }
     }
 }