【剑指Offer】和为S的两个数字（二分查找）

梦里梦外; 2022-03-14 14:20 100阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_390da4f7a00f44bea7c2f3d19491311b_tpId_13_tqId_11195_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

##### 输出描述: #####

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

#### 解决方法 ####

class Solution { 
    public:
        vector<int> FindNumbersWithSum(vector<int> array,int sum) { 
            //二分查找变体，设置两个指针，一前一后判断两个数字之和与S比较，时间复杂度O(n)
            //如果有多对数字的和等于S，则乘积最小的必定是距离相差最大的那一对，可证明
            int left=0,right=array.size()-1;
            vector<int> ans;
            while(left<right){ 
                if(array[left]+array[right]==sum){ ans.push_back(array[left]);ans.push_back(array[right]);break;}
                else if(array[left]+array[right]>sum) right--;
                else left++;
            }
            return ans;
        }
    
    };

[https_www.nowcoder.com_practice_390da4f7a00f44bea7c2f3d19491311b_tpId_13_tqId_11195_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，100人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer--和为s的两个数字

题目描述输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。示例 1：输入：nums =

冷不防/ 2023年02月18日 08:12/ 0 赞/ 16 阅读

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

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

Bertha 。/ 2022年08月09日 02:18/ 0 赞/ 130 阅读

相关剑指offer—-和为S的两个数字

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

末蓝、/ 2022年07月19日 05:20/ 0 赞/ 151 阅读

相关剑指Offer | 和为S的两个数字

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

以你之姓@/ 2022年05月23日 11:35/ 0 赞/ 140 阅读

相关剑指offer 和为S的两个数字

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

待我称王封你为后i/ 2022年05月21日 05:18/ 0 赞/ 139 阅读

相关剑指offer:和为S的两个数字

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

谁借莪１个温暖的怀抱￠/ 2022年04月10日 09:17/ 0 赞/ 156 阅读

相关【剑指Offer】和为S的两个数字（二分查找）

题目链接：[https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11

梦里梦外;/ 2022年03月14日 14:20/ 0 赞/ 101 阅读

相关剑指Offer-和为S的两个数字

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

傷城~/ 2022年02月18日 14:09/ 0 赞/ 174 阅读

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

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

阳光穿透心脏的1/2处/ 2021年12月17日 16:03/ 0 赞/ 214 阅读

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

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

深藏阁楼爱情的钟/ 2021年12月09日 01:09/ 0 赞/ 188 阅读