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

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

分析

今天上课，老师说了，在面试的时候不要一上来就去找最优的解法，因为你一时半会儿可能会找不到最优的。而且就算立即做出来了，面试官会认为你以前刷过这道题。所以可以先将最简单的思路哪怕是暴力穷举也可以告诉面试官，然后在逐步去寻找最优解。

这道题的最简单办法是遍历数组，每到一个数字，就去遍历它后面的数字，直到找到两个数的和等于s即可。

然而这种方法的时间复杂度是O(n²)。并且没有用的排序数组这个特性。

更好一点的办法是设立两个指针i和j分别指向数组的头和尾。我们比较他们两个数的和，如果大于给定的数字sum，则可推断出j及其后面的数字和i相加都会大于sum，所以我们把j减1，也就是向移动一个数字。同理，如果两个数字之和小于给定的数字，我们就把i加1.

基于以上分析，写出代码如下：

```bool FindNumbersWithSum(const vector& v,int sum,int& n1,int& n2) { int left=0,right=v.size()-1; while(left<=right) { if(v[left]+v[right]==sum) { n1=v[left]; n2=v[right]; return true; } else if(v[left]+v[right]>sum) { right--; } else { left++; } } return false; }

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

* * *

### 分析

和上一道题一样，我们也可以设置两个指针i和j，只不过他两被初始化为1和2.然后在一个循环中我们判断i+…+j是否等于给定的数字sum？是，就打印从i到j的所有数字.否则，如果i+…+j>sum，就令i加1；否则就令j+1(i+…+j<sum)。循环直到i超过了sum/2就结束。

<img src="/images/test.png" width="100%" height="100%">

代码如下：

```void print(int left,int right)
{
    int i;
    for(i=left;i<=right;++i)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}

bool FindContinuousSequence(int sum)
{
    if(sum<3)
        return false;
    int middle=(sum+1)/2;
    int left=1,right=2;
    int cursum=left+right;
    while(left<=middle)
    {
        if(cursum==sum)
        {
            print(left,right);
            cursum-=left;
            left++;
        }
        else if(cursum<sum)
        {
            right++;
            cursum+=right;
        }
        else
        {
            cursum-=left;
            left++;
        }
    }
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往(题目一)  点我前往(题目二)