跟为S的两个数字
和为S的两个数字
- 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
何海涛:《剑指Offer:名企面试官精讲典型编程题》:九度OJ
题目描述:http://ac.jobdu.com/problem.php?cid=1039&pid=23
- 输入:
-
每个测试案例包括两行:第一行包含一个整数n和k,n表示数组中的元素个数,k表示两数之和。其中1 <= n <= 10^6,k为int第二行包含n个整数,每个数组均为int类型。
- 输出:
- 对应每个测试案例,输出两个数,小的先输出。如果找不到,则输出“-1 -1”
- 样例输入:
-
6 15 1 2 4 7 11 15
样例输出:
4 11
思想:因为已经排好序,那么如果存在那么两个数,可能是一个比较大,一个比较小,或者是比较相等的两个数!所以我们设一个n1=min(即a[0]),n2=max( 即a[n-1] )开始,实际是n1 = a[low],low=0开始,n2 = a[high],high=n-1开始,然后n1+n2与S(我们需要的和)进行比较,若>,则n2
=a[--high];若<, n1=a[++low],若==,则使用mul保存乘积,还要保存两个数,因为可能不只一对数,它只要乘积小的!扫描直到low>=high终止!
代码AC:
#include <stdio.h> #include <stdlib.h> int main() { long int n, i, low, high; long long int mul; long int s, *data, m1, m2, flag; while(scanf("%ld%ld", &n, &s) != EOF ) { data =( long int* )malloc( sizeof( long int ) * n ); for( i = 0; i < n; i++ ) // { scanf("%ld", &data[i]); } m1 = -1; m2 = -1; low = 0; high = n - 1; mul = -1; flag = 1; while( low < high ) // 注意:负数和重复的数字( 可以无视 ) { if( data[low] + data[high] > s ) { high--; } else if( data[low] + data[high] < s ) { low++; } else { if( flag ) { mul = data[low] * data[high]; m1 = data[low]; m2 = data[high]; flag = 0; } else { if( mul > data[high] * data[low] ) { mul = data[high] * data[low]; m1 = data[low]; m2 = data[high]; } } // printf("%d %d\n", data[low], data[high]); low++; high--; } } printf("%ld %ld\n", m1, m2); free( data ); } return 0; }