【剑指】递增数组和为s的两个数

浅浅的花香味﹌ 2023-07-01 09:00 27阅读 0赞

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

思路：首先是递增数组。为了程序的健壮性，  
首先我们判断s是否小于数组的最小值a\[0\]，小于返回空。  
其二数组 是不是空的，如果非空，数组个数是否大于1？  
我们还是通过活动夹逼方式，从最小值+最大值开始，和大于了s，右边–。和小于了s，左边++。**直到相等，相等时两者同时（左++，右–）但是！后来发现，两个数相距越远，乘积越小**，所以将发现的第一对就直接返回

代码：

class Solution { 
        //数字越近乘积越小
    public:
        vector<int> FindNumbersWithSum(vector<int> array,int sum) { 
            int n=array.size();
            vector<int> res;
            if(n<=1)    return res;
            if(sum< array[n-1] || array[0]> sum)
                return res;
            int left=0,right=n-1;
            
            while(left<right)
            { 
                if(array[left]+array[right]>sum)
                { 
                    right--;
                }
                else if(array[left]+array[right]<sum)
                    left++;
                else
                { 
                    res.push_back(array[left++]);   //实现小的先输出
                    res.push_back(array[right--]);
                    return res;
                }
            }
            
            
        }
    };

//遍历一遍 o(n)  
扩展，如果不是递增的顺序，是随机的。1，可以先排序然后活动变化窗口；2，哈希表，数组建b，键值为【s-a\[i\]】,里面值为0，然后遍历数组a，为b中元素加一，如：s==100. b\[97\]=0. a\[0\]==97, a\[4\]==3,: b\[a\[i\] \]++.再遍历数组，为一的输出。