题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
思路整理一下：最初我们找到数组的第一个数字和最后一个数字。首先定义两个指针，第一个指针指向数组的第一个（也就是最小的）数字，第二个指针指向数组的最后一个（也就是最大的）数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。
|
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
|
bool
FindNumbersWithSum(
int
data[],
int
length,
int
sum,
int
*num1,
int
*num2)
{
bool
found =
false
;
if
(length < 1 || num1 == NULL || num2 == NULL)
return
false
;
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;
}
|
测试代码：
题目：输入一个正数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为止。
|
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
|
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);
}
big++;
curSum += big;
}
}
void
PrintContinuousSequence(
int
small,
int
big)
{
for
(
int
i = small; i <= big; ++i)
printf
(
"%d "
, i);
printf
(
"\n"
);
}
|
扩展：
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。
|
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
|
#include<list>
#include<iostream>
using
namespace
std;
list<
int
>list1;
void
find_factor(
int
sum,
int
n)
{
// 递归出口
if
(n <= 0 || sum <= 0)
return
;
// 输出找到的结果
if
(sum == n)
{
// 反转list
list1.reverse();
for
(list<
int
>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter <<
" + "
;
cout << n << endl;
list1.reverse();
}
list1.push_front(n);
//典型的01背包问题
find_factor(sum-n, n-1);
//放n，n-1个数填满sum-n
list1.pop_front();
find_factor(sum, n-1);
//不放n，n-1个数填满sum
}
int
main()
{
int
sum, n;
cout <<
"请输入你要等于多少的数值sum:"
<< endl;
cin >> sum;
cout <<
"请输入你要从1.....n数列中取值的n："
<< endl;
cin >> n;
cout <<
"所有可能的序列，如下："
<< endl;
find_factor(sum,n);
return
0;
}
|
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3642455.html，如需转载请自行联系原作者
