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

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

 vector<int> findNumberwWithSum(vector<int>&data, int sum)

 {

     int n = data.size();

     vector<int>result;

     if (n < )

         return result;

     int left = , right = n-;

     while (left < right)

     {

         if (data[left]+data[right] == sum)

         {

             result.push_back(data[left]);

             result.push_back(data[right]);

             break;

         }

         else if (data[left]+data[right] < sum)

             ++left;

         else

             --right;

     }

     return result;

 }

题目二：输入一个正数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 < )

        return ;

     int small = ;

     int big = ;

     int middle = ( + sum) /;

     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;

         }

     }

 }

巴特西

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

最新文章

热门文章