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

和为s的两个数字

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

有点类似于夹逼的思想

注意两个int相加的和要用long long类型比较规范

 1 bool FindNumbersWithSum(int data[], int length, int sum,
 2                         int* num1, int* num2)
 3 {
 4     if (data == NULL || length < 2)
 5         return false;
 6 
 7     int i = 0;
 8     int j = length - 1;
 9     while (i < j)
10     {
11         long long tempSum = data[i] + data[j];
12         if (tempSum == sum)
13         {
14             *num1 = data[i];
15             *num2 = data[j];
16             return true;
17         }
18         else if (tempSum > sum)
19             j--;
20         else
21             i++;
22     }
23     return false;
24 }

和为s的连续正数序列

题目：输入一个正数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为止。

 1 void FindContinuousSequence(int sum)
 2 {
 3     if(sum < 3)
 4         return;
 5      
 6     int small = 1;
 7     int big = 2;
 8     int middle = (1 + sum) / 2;
 9     int curSum = small + big;
10      
11     while(small < middle)
12     {
13         if(curSum == sum)
14             PrintContinuousSequence(small, big);
15          
16         while(curSum > sum && small < middle)
17         {
18             curSum -= small;
19             small++;
20              
21             if(curSum == sum)
22                 PrintContinuousSequence(small, big);
23         }
24          
25         big++;
26         curSum += big;
27          
28     }
29 }
30  
31 void PrintContinuousSequence(int small, int big)
32 {
33     for(int i = small; i <= big; ++i)
34         printf("%d ", i);
35     printf("
");
36 }

普通方法：

vector<vector<int> > FindContinuousSequence(int sum) {
    vector<vector<int> > result;
    int i = 1;
    int j;
    while (i <= sum / 2)
    {
        int j = i + 1;
        int curSum = i + j;
        while (curSum <= sum)
        {
            if (curSum == sum)
            {
                vector<int> tmp;
                for (int q = i; q <= j; q++)
                    tmp.push_back(q);
                result.push_back(tmp);
                break;
            }
            else
            {
                j++;
                curSum += j;
            }
        }
        i++;
    }
    return result;
}

高效率：