和为S的两个数字

深藏阁楼爱情的钟 2022-03-20 03:28 252阅读 0赞

**何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ**

**题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=23][http_ac.jobdu.com_problem.php_cid_1039_pid_23]**

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

**输入：**

每个测试案例包括两行：

第一行包含一个整数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;
    }

[http_ac.jobdu.com_problem.php_cid_1039_pid_23]: http://ac.jobdu.com/problem.php?cid=1039&pid=23