剑指offer：和为S的两个数字

阳光穿透心脏的1/2处 2021-12-17 16:03 279阅读 0赞

题目描述：

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

输出描述：

对应每个测试案例，输出两个数，小的先输出。

思路分析：

1. 最直接的分析是对于数组中的每个数，都去和它后面的数相加，判断是否和为S。那这样的时间复杂度为O(n^2)，超时。

2. 其实思路很简单，但是自己一直没想到。用头尾两个指针，由于数组有序，那么第一个元素就最小，最后一个元素就最大。将当前两个指针所指的元素相加，判断若大于S，则右指针前移，若小于S，则左指针后移。而当相等时，就判断是否为第一对满足情况的数，若是直接保存，否则再进行一次两对满足要求数的乘积比较，保留较小的。这样的时空复杂度都仅为O(n)。

代码：

直接放后一个思路的代码。

1 class Solution {
     2 public:
     3     vector<int> FindNumbersWithSum(vector<int> array,int sum) {
     4         vector<int> res;
     5         int len = array.size();
     6         if(len<2)
     7             return res;
     8         int l,r;
     9         l = 0;
    10         r = len-1;
    11         while(l<r)
    12         {
    13             if(array[l]+array[r]>sum)
    14             {
    15                 r--;
    16             }
    17             else if(array[l]+array[r]<sum)
    18             {
    19                 l++;
    20             }
    21             else
    22             {
    23                 if(res.size()==0)
    24                 {
    25                     res.push_back(array[l]);
    26                     res.push_back(array[r]);
    27                 }
    28                 else
    29                 {
    30                     if(res[0]*res[1]>array[l]*array[r])
    31                     {
    32                         res[0] = array[l];
    33                         res[1] = array[r];
    34                     }
    35                 }
    36                 l++;
    37                 r--;
    38             }
    39         }
    40         return res;
    41     }
    42 };

转载于:https://www.cnblogs.com/LJ-LJ/p/11028452.html