题目链接

牛客网

题目描述

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

返回值描述:

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

解题思路

方法一：哈希法

要求a + b = sum, 如果已知a， 那么b = sum - a
所以可以先将b添加入哈希中，然后遍历一遍数组设为a， 在哈希中寻找是否存在sum-a，返回找到的第一对数据。

  1. class Solution {
  2. public:
  3.     vector<int> FindNumbersWithSum(vector<int> array,int sum) {
  4.         vector<int> ret;
  5.         if(array.empty())
  6.             return ret;
  7.         map<int, int> mp;
  8.         //unordered_map效率更高，但是牛客网好像不支持
  9.         //unordered_map<int,int> mp;
  10.         for(int i=0;i<array.size();++i){
  11.             mp[array[i]] = i;
  12.         }
  13.         for(int i=0;i<array.size();++i){
  14.             // 找到第一个，返回
  15.             if(mp.find(sum - array[i])!=mp.end()){
  16.                 int j = mp[sum - array[i]];
  17.                 return vector<int> ({array[i],array[j]});
  18.             }
  19.         }
  20.         return ret;
  21.     }
  22. };
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

    方法二：双指针

使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

  • 如果两个指针指向元素的和 ==sum，那么这两个元素即为所求。
  • 如果 和 > sum，移动较大(—j)的元素，使 和 变小一些；
  • 如果 和 < sum，移动较小(++i)的元素，使 和 变大一些。
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        // 判断特殊情况返回
        if(array.empty())
            return ret;
        // 给i和j赋初值
        int left=0,right=array.size()-1;
        // 排除掉右边大于sum的值
        while(array[right] > sum)
            right--;
        while(left<right){
            if(array[left]+array[right]==sum){
                return {array[left],array[right]};
            }
            if(array[left]+array[right]<sum)
                left++;
            if(array[left]+array[right]>sum){
                right--;
            }
        }
        return {};
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)