【面试题041】和为s的两个数字VS和为s的连续正数序列
题目一：
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
思路一：
现在数组中固定一个数字，再依次判断数组中其他的n-1个数字与它的和是不是等于s，
——时间复杂度O(n)
思路二：
在数组中选择两个数字，如果他们的和等于s那么就找到了，
如果小于s呢，显然我们希望和更大一些，由于数组有序，可以考虑较小数字的后面的数字。因为排在后面的数字更大一些。就有可能等于s。
如果大于s呢，我们可以考虑选择较大数字前面的那个数字，因为排在前面的那个数字更小一些。
——初始化时候定义两个指针，一个指向第一个元素，一个指向最后一个元素。
——从两段向中间扫面数组，时间爱你复杂度是O(n)。
|
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
37
38
39
40
41
42
43
44
45
46
47
|
|
#include <iostream>
using namespace std;
bool FindNumberWithSum(int data[], int length, int sum, int *num1, int *num2)
{
bool found = false;
if (length < 1 || num1 == NULL || num2 == NULL)
{
return found;
}
int ahead = length - 1;
int behind = 0;
while (ahead > behind)
{
long long curSum = data[ahead] + data[behind];
if (curSum == sum)
{
*num1 = data[behind];
*num2 = data[ahead];
found = true;
break;
}
else if (curSum > sum)
{
ahead --;
}
else
{
behind ++;
}
}
return found;
}
int main()
{
int num1, num2;
int data[] = {1, 2, 4, 7, 11, 15};
int length = sizeof(data) / sizeof(data[0]);
int sum = 15;
if (FindNumberWithSum(data, length, sum, &num1, &num2))
{
cout << num1 << " " << num2 << endl;
}
return 0;
}
|
题目二：
输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数字）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，
所以打印出3个连续序列1~5，4~6和7~8。
思路一：
和前面的思路一样，初始化samll为1，big为2，因为至少两个数字，和和s比较，
如果从samll到big的序列小于s，你们增加big，好让这个序列包含更多的数字，
如果从samll到big的序列大于s，那么考虑去掉一些数字，把small增大1，
如果正好等于s，那么把他打印出来。然后继续增加samll，
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
|
#include <iostream>
using namespace std;
void PrintContinuousSequence(int small, int big)
{
for (int i = small; i <= big; ++i)
{
cout << i << " ";
}
cout << endl;
}
void FindContinuousSequence(int sum)
{
if (sum < 3)
{
return ;
}
int small = 1;
int big = 2;
int middle = (1 + sum) / 2;
int curSum = small + big;
while (small < middle)
{
if (curSum == sum)
{
PrintContinuousSequence(small, big);
}
while (curSum > sum && small < middle)
{
curSum -= small;
small ++;
if (curSum == sum)
{
PrintContinuousSequence(small, big);
}
}
//运行到这里一定是curSum > sum的情况
big ++;
curSum += big;
}
}
int main()
{
FindContinuousSequence(15);
return 0;
}
|