找出满足条件的数

方法很简单，先对数组排序，时间复杂度为O(nlogn)，然后用两个指针分别指向数组的首位和末尾，将首末两数相加和为S，如果S等于给定的数SUM则记录，如果S>SUM则尾指针减一，如果S<SUM则首指针加一，直到首指针大于等于尾指针。总的时间复杂度为O(nlogn)+O(n)=O(nlogn)，代码如下：

int FindNumsSum(int arr[], int n, int sum, int recd[10][2])
{
	bool flag=false;
	if(arr==NULL || n<1 || recd==NULL)
		return 0;
	InsertSort(arr,n);
	for(int k=0;k<n;k++)
	{
		printf("%d ",arr[k]);
	}
	printf("\n");
	int i=0,j=n-1;
	int m=0;
	while(i<j)
	{
		if(arr[i]+arr[j]==sum)
		{
			recd[m][0]=arr[i];
			recd[m][1]=arr[j];
			m++;
			i++;
			flag=true;
		}
		else if(arr[i]+arr[j]<sum)
		{
			i++;
		}
		else
		{
			j--;
		}
	}
	if(flag)
		return m;
	return 0;
}

2、输出所有和为整数S的连续正数序列，如输入15 ，则1+2+3+4+5=4+5+6=7+8=15，输出（1，2，3，4，5），（4，5，6），（7，8）

有了上述的思想，该题目也可以利用首尾数字的移动来实现。

比如输入数字s=15：

(1)令a0=1,a1=2;

(2)判断a0+a1==s? ,如果a0+a1<s则a1向后加1,即a1++，如果a0+a1>s，则a0向后加1，并舍去a0前面的数字，知道a1>=(s+1)/2，具体步骤如下：

 1+2<15

1+2+3<15

1+2+3+4<15

1+2+3+4+5==15 找到第一组

1+2+3+4+5+6>15

2+3+4+5+6>15

3+4+5+6>15

4+5+6==15 找到第二组

4+5+6+7>15

5+6+7>15

6+7<15

6+7+8>15

7+8==15 找到第三组，退出

实现代码如下：

void PrintResults(int a, int b)
{
	if(a>=b)
		return;
	for(int i=a;i<=b;i++)
	{
		printf("%d, ",i);
	}
	printf("\n");
}
void FindContinuousSequence(int sum)
{
	if(sum<3)
		return;
	int a0=1;
	int a1=2;
	int mid=(1+sum)/2;
	int tmpsum=a0+a1;
	while(a0<mid)
	{
		if(tmpsum==sum)
		{
			PrintResults(a0,a1);
		}
		while(tmpsum>sum && a0<mid)
		{
			tmpsum-=a0;
			a0++;
			if(tmpsum==sum)
			{
				PrintResults(a0,a1);
			}
		}
		a1++;
		tmpsum+=a1;
	}
}  

找出满足条件的数,布布扣,bubuko.com

找出满足条件的数

原文：http://blog.csdn.net/cdj0311/article/details/22756971