和為S的兩個數字VS和為S的連續正數序列，vs正數

和為S的兩個數字VS和為S的連續正數序列，vs正數

題目：輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等於s，輸出任意一對即可。

思路:最初我們找到數組的第一個數字和最後一個數字。首先定義兩個指針，第一個指針指向數組的第一個（也就是最小的）數字，第二個指針指向數組的最後一個（也就是最大的）數字。當兩個數字的和大於輸入的數字時，把較大的數字往前移動；當兩個數字的和小於數字時，把較小的數字往後移動；當相等時，打完收工。這樣掃描的順序是從數組的兩端向數組的中間掃描。

#include "stdafx.h"
#include<iostream>

bool FindNumbersWithSum(int data[], int length, int sum, int* num1, int* num2)
{
    bool found = false;
    if(length < 1 || num1 == NULL || num2 == NULL)
        return found;

    int ahead = length -1;
    int behind = 0;

    while(ahead > behind)
    {
        long long curSum = data[ahead] + data[behind];

        if(curSum == sum)
        {
            *num1 = data[behind];
            *num2 = data[ahead];
            found = true;
            break;
        }
        else if(curSum > sum)
            ahead --;
        else
            behind ++;
    }

    return found;
}

int main()
{
    int data[] = {1,2,4,7,11,15};
    int length = sizeof(data)/sizeof(int);
    int sum = 15;
    int num1, num2;
    int result = FindNumbersWithSum(data, length, sum, &num1, &num2);
    if(result)
    {
        if(num1 + num2 == sum)
            printf("%d  %d\n", num1, num2);
        else
        printf("Failed.\n");
    }
    else
        printf("Failed.\n");
    
    return 0;
}

題目：輸入一個正數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 #include "stdafx.h"
 2 
 3 void PrintContinuousSequence(int small, int big);
 4 
 5 void FindContinuousSequence(int sum)
 6 {
 7     if(sum < 3)
 8         return;
 9     
10     int small = 1;
11     int big = 2;
12     int middle = (1 + sum) / 2;
13     int curSum = small + big;
14     
15     while(small < middle)
16     {
17         if(curSum == sum)
18             PrintContinuousSequence(small, big);
19             
20         while(curSum > sum && small < middle)
21         {
22             curSum -= small;
23             small ++;
24             
25             if(curSum == sum)
26                 PrintContinuousSequence(small, big);
27         }
28         
29         big ++;
30         curSum += big; 
31     }
32 }
33 
34 void PrintContinuousSequence(int small, int big)
35 {
36     for(int i = small; i <= big ; i ++)
37         printf("%d ", i);
38 
39     printf("\n");
40 }
41 
42 int main(int argc, char const *argv[])
43 {
44     int sum = 9;
45     printf("test for %d:\n", sum);
46     FindContinuousSequence(sum);
47     
48     sum = 15;
49     printf("test for %d:\n", sum);
50     FindContinuousSequence(sum);
51     
52     sum = 100;
53     printf("test for %d:\n", sum);
54     FindContinuousSequence(sum);
55 
56     return 0;
57 }