题目：输入一个递增排序的数组和一个数字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;} |
测试代码：
|
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
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;}int
main(){ int
data[] = {1, 2, 4, 7, 11, 15}; int
length = sizeof(data) / sizeof(int); int
num1, num2; bool
result = FindNumbersWithSum(data, length, 15, &num1, &num2); if(result) { cout<<"num1:"<<num1<<endl; cout<<"num2:"<<num2<<endl; } else cout<<"failed!"<<endl; return
0;} |
题目：输入一个正数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");} |
和为S的两个数字VS和为s的连续正数序列,布布扣,bubuko.com
原文：http://www.cnblogs.com/heyonggang/p/3642455.html