题目出处http://blog.csdn.net/v_JULY_v/article/details/6419466
O(N)时间复杂度 HASH表的用处得以体现
// FindSum.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#define N 6
#define M 1000
int array[N]={1,2,4,7,11,15};
int hash[M];
int main(int argc, char* argv[])
{
int pos;
int i;
for(i = 0; i < N; i++) //构建hash表
{
pos = array[i] % M;
hash[pos]++;
}
int n;
scanf("%d", &n);
for(i = 0; i < N; i++)
{
pos = (n - array[i]) % M;
if (hash[pos])
{
if (pos == array[i] && hash[pos] > 1)
{
printf("%d %d", array[i], pos);
break;
}
else if (pos != array[i])
{
printf("%d %d", array[i], pos);
break;
}
}
}
return 0;
}
二.2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来。
#include "stdio.h"
int n;
int m;
int array[1000]={0};
void Print()
{
int flag = 0;
for(int i = 1; i < n; i++)
{
if (!flag && array[i])
{
printf("%d",i);
flag = 1;
}
else if (array[i])
printf("+%d",i);
}
printf("\n",i);
}
void FindSum(int num, int sum)//m是当前的数，sum是和
{
if (num > n || sum > m)
return;
if (sum == m)
{
Print();
return;
}
array[num] = 1;
FindSum(num+1, sum+num); //取m
array[num] = 0;
FindSum(num+1, sum); //不取m
}
void main()
{
printf("n:");
scanf("%d", &n);
printf("m:");
scanf("%d", &m);
FindSum(1, 0);
}