【剑指Offer】面试题41:和为S的两个数

xiaoxiao2021-02-28  124

一:题目描述

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

输出描述:

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

二:解体分析

最简单的方法,两层for循环,但时间复杂度高

可以采用夹逼的方式,利用两个指针分别指向数组的首位,如果两个数的和大于sum,指向尾部的指针--,如过小于sum,指向头部的指针++,直到找到相等或者start==end结束

对于题目中说多对满足的情况,举例发现,最开始满足条件的对,乘积最小,如

1,2,3,4,5,6,7,8,9       找和为9的两个数

数1   数2  乘积

1,8 ,   8

2,7,    14

3,6,    18

4,5 ,  20

三:代码实现

class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { vector<int> result; if(array.size()<=1) return result; if(array.size()>=2 && array[0]>sum) return result; int start=0; int end=array.size()-1; while(start<end){ if(array[start]+array[end]>sum) end--; else if(array[start]+array[end]<sum) start++; else{ result.push_back(array[start]); result.push_back(array[end]); break; } } return result; } };

转载请注明原文地址: https://www.6miu.com/read-44046.html

最新回复(0)