题解 | #和为S的两个数字#

条件：数组非递减排序（测试案例中并非只有题目中所说的非递增排序）
思路：首先，若给定数组为空，则返回空
其次，先找到数组中数值接近目标值一半的元素下标，以此为中心向两边拓展查找范围，找出所有可能
最后，由于结果数组中元素应该是两两为一对，因此计算所有可能解得乘积，再找出乘积最小值并记录位置，然后反推出答案数组中的所对应的实际元素。

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        if(array.empty()) return vector<int> ();
        vector<int> ans;
        int i=0, temp=0;
        while(temp==0)
        {
            if((array[i]<=sum/2) && (array[i+1]>=sum/2))
                temp = i;
            i++;
        }

        int first = temp;
        int last = temp+1;
        while(first>=0 && last<array.size())
        {
            if((array[first]+array[last]) > sum)
                --first;
            else if((array[first]+array[last]) < sum)
                last++;
            else
            {
                ans.push_back(array[first]);
                ans.push_back(array[last]);
                first--;
            }
        }

        if(first<-1 || last>array.size() || ans.empty())
            return {};

        if(ans.size()==2)
            return ans;
        else
        {
            vector<int> mul;
            for(int i=0;i<ans.size()/2;i++)
                mul.push_back(ans[2*i]*ans[2*i+1]);

            int cnt=0;
            int num=mul[0];
            for(int j=1;j<mul.size();j++)
            {
                if(num>mul[j])
                {
                    num=mul[j];
                    cnt=j;
                }
            }

            vector<int> comp;
            comp.push_back(ans[2*cnt]);
            comp.push_back(ans[2*cnt+1]);
            return comp;
        }
    }
};

时间复杂度：O(n)
空间复杂度：O(n)