《剑指offer》面试题57：和为s的两个数字（扩展）

更多剑指offer面试习题请点击：《剑指offer》（第二版）题集目录索引

题目1：和为s的两个数字

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

解题思路：
　　用start和end来做标记，开始时分别标记数组的首、尾元素。比较这两个数之和sum与s的大小，如果sum<s，那么让start++，标记数组的第二个元素；如果sum>s，那就让end--，标记数组的倒数第二个元素。再比较start和end标记的数之和与s的大小。重复上述步骤，直到sum==s为止。

< Code>

/*
 * 功能：
 *   找出数组中两个和等于s的数
 *
 * 参数：
 *   arr[]：数组名
 *   size： 数组元素个数
 *   sum：  指定的数
 *   num1： 整数指针变量，保存数字1
 *   num2： 整数指针变量，保存数字2
 *
 * 返回值：
 *   成功返回true
 *   失败返回false
 */
bool FindNumbersWithSum(int arr[], size_t size, int sum, int* num1, int* num2)
{
    //标记，查找是否成功
    bool find = false;  

    if (arr == nullptr || size < 1 || num1 == nullptr || num2 == nullptr)
    { 
        //参数不合法
        return find;
    }

    int start = 0; 
    int end = size - 1;

    while (start < end){

        int curSum = arr[start] + arr[end];

        if (curSum == sum){   //两数之和 = 目标值
            *num1 = arr[start];
            *num2 = arr[end];
            find = true;
            break;
        }
        else if (curSum < sum){  //两数之和 < 目标值
            start++;
        }
        else if (curSum > sum){  //两数之和 > 目标值
            end--;
        }
    }
    return find;
}

< TestCode>

void Test(char* testName, int arr[], size_t size, int sum, bool expectedReturn)
{
    if (testName != nullptr){
        printf("%s begin：\n", testName);
    }

    int num1 = 0;
    int num2 = 0;
    size_t size = sizeof(arr) / sizeof(arr[0]);
    bool result = FindNumbersWithSum(arr, size, sum, &num1, &num2);

    if (result == expectedReturn){
        if (result){
            if (sum == num1 + num2){
                printf("passed!\n");
            }
            else{
                printf("FAILED!\n");
            }
        }
        else{
            printf("FAILED!\n");
        }
    }
    else{
        printf("FAILED!\n");
    }
}

// 存在和为s的两个数字，这两个数字位于数组的中间
void Test1()
{
    int data[] = { 1, 2, 4, 7, 11, 15 };
    Test("Test1", data, sizeof(data) / sizeof(int), 15, true);
}

// 存在和为s的两个数字，这两个数字位于数组的两段
void Test2()
{
    int data[] = { 1, 2, 4, 7, 11, 16 };
    Test("Test2", data, sizeof(data) / sizeof(int), 17, true);
}

// 不存在和为s的两个数字
void Test3()
{
    int data[] = { 1, 2, 4, 7, 11, 16 };
    Test("Test3", data, sizeof(data) / sizeof(int), 10, false);
}

// 鲁棒性测试
void Test4()
{
    Test("Test4", nullptr, 0, 0, false);
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();

    system("pause");
    return 0;
}

< TestResult>

---

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

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

解题思路：
　　这题还是利用start和end两个标记，不过开始时start标记为1，end标记为2。sum还是记录start和end之和。
　　如果sum<s，让end++;，然后让sum+=end;
　　如果sum<s，让sum-=start;让后start++;。
　　如果sum==s，这时候就打印start~end，让后让end++;，继续寻找一个符合要求的序列。

< Code>

void PrintContinuousSequence(int start, int end)
{
    int i = start;
    for (; i <= end; ++i){
        printf("%d ", i);
    }
    printf("\n");
}

void FindContinuousSequence(int sum)
{
    if (sum < 3){
        return;
    }

    int start = 1;
    int end = 2;
    int mid = (sum + 1) >> 1;  //序列中所有数都会小于等于sum的一半
    int curSum = start + end;

    while (start <= mid && end <= mid){
        if (sum == curSum){  
            PrintContinuousSequence(start, end);
            ++end; //寻找下一个符合标准的序列
            curSum += end;
        }
        else if (sum > curSum){
            ++end; 
            curSum += end;
        }
        else if (sum < curSum){
            curSum -= start;
            ++start;
        }
    }
}

< TestCode>

void Test(const char* testName, int sum)
{
    if (testName != nullptr)
        printf("%s for %d begins: \n", testName, sum);

    FindContinuousSequence(sum);
    printf("\n---------------------------------------------------\n");
}

int main()
{
    Test("test1", 1);
    Test("test2", 3);
    Test("test3", 4);
    Test("test4", 9);
    Test("test5", 15);
    Test("test6", 100);

    system("pause");
    return 0;
}

< TestResult>