和为S的两个数字

50 阅读 0 评论 33 点赞

我是靠谱客的博主自然饼干，最近开发中收集的这篇文章主要介绍和为S的两个数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
思路： a+b=c;st a*b尽可能的小，根据常识，a,b之间的差越大，乘积越小，（换个角度想，给你周长一定，怎么样的四边形的面积最大，肯定是正方形），根据这个想法（前提是递增排序的数组），从头尾开始寻找起，如果刚好相等，则返回，如果<,则跳出本次循环，如果>，则结束本次循环，结合代码来看

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.empty()) return res;
        for(int i = 0;i<array.size();i++)
        {
            for(int j = array.size()-1;j>i;--j)
            {
                if(array[i]+array[j]==sum)
                {
                    res.push_back(array[i]);
                    res.push_back(array[j]);
                    return res;
                }
                else if(array[i]+array[j]<sum)
                {
                    break;
                }
                else
                {
                    continue;
                }
            }
        }
        return res;
    }
};

精简下代码,上述代码的思路,如果大于sum，j–,如果小于,i++;
根据这个思路，精简下代码，如下：（有没有想起夹逼准则。。。）

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> res;
        if(array.empty()) return res;
        int i = 0,j=array.size()-1;
            while(i<j)
            {
                if(array[i]+array[j]==sum)
                {
                    res.push_back(array[i]);
                    res.push_back(array[j]);
                    return res;
                }
                while(i<j&&array[i]+array[j]>sum)j--;
                while(i<j&&array[i]+array[j]<sum)i++;
            }
        return res;
    }
};