题目出处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); }