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

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


分析

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

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

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

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

基于以上分析,写出代码如下:

{
    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就结束。

啊啊啊啊

代码如下:

{
    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上:点我前往(题目一)  点我前往(题目二)

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")