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

<div style="visibility: hidden; overflow: hidden; position: absolute; top: 0px; height: 1px; width: auto; padding: 0px; border: 0px; margin: 0px; text-align: left; text-indent: 0px; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal;"><div id="MathJax_Hidden"></div></div><div id="MathJax_Message" style="display: none;"></div>

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


分析

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

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

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

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

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

FindNumbersWithSum(const vector<int>& v,int sum,int& n1,int& n2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
int left=0,right=v.size()-1;
while(left&lt;=right)
{
if(v[left]+v[right]==sum)
{
n1=v[left];
n2=v[right];
return true;
}
else if(v[left]+v[right]&gt;sum)
{
right--;
}
else
{
left++;
}
}
return false;
}

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


分析

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

啊啊啊啊

代码如下:

print(int left,int right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
{
int i;
for(i=left;i&lt;=right;++i)
{
cout&lt;&lt;i&lt;&lt;" ";
}
cout&lt;&lt;endl;
}
bool FindContinuousSequence(int sum)
{
if(sum&lt;3)
return false;
int middle=(sum+1)/2;
int left=1,right=2;
int cursum=left+right;
while(left&lt;=middle)
{
if(cursum==sum)
{
print(left,right);
cursum-=left;
left++;
}
else if(cursum&lt;sum)
{
right++;
cursum+=right;
}
else
{
cursum-=left;
left++;
}
}
}

以上

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

完整代码及测试用例在github上:点我前往(题目一)  点我前往(题目二) <div style="position: absolute; width: 0px; height: 0px; overflow: hidden; padding: 0px; border: 0px; margin: 0px;"><div id="MathJax_Font_Test" style="position: absolute; visibility: hidden; top: 0px; left: 0px; width: auto; padding: 0px; border: 0px; margin: 0px; white-space: nowrap; text-align: left; text-indent: 0px; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; font-size: 40px; font-weight: normal; font-style: normal; font-family: MathJax_Math-italic, sans-serif;"></div></div>

<div>来自为知笔记(Wiz)</div>