输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，我们可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使

admin2017-11-20 96

问题输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，我们可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：
说明你所设计算法的时间复杂度。

选项

答案时间复杂度分析：在while的循环中，每次根据curSum和sum之间的大小关系来决定改变ahead还是改变behind。这个过程每次是O(1)的。在整个算法流程中，因为ahead始终大于behind的，如果一个数被ahead扫过了，那么它不会被behind扫到，也不会被ahead再次扫到；同样的，如果一个数被behind扫过了，那么它将不会再被ahead或者behind扫到。所以循环最多执行n-1次就会结束，故整个算法的时间复杂度为O(n)。

解析

转载请注明原文地址:https://kaotiyun.com/show/9VRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

战国时期的著名水利工程“郑国渠”位于今天的()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

中华人民共和国恢复了在联合国合法席位的时间是()。

洪武年间修复过的水利工程有()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

试析淝水之战前后南北政权的特点和变化。

以孙中山为首的革命派和以康有为代表的维新派，是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()

A．卫生法律B．卫生行政法规C．卫生行政规章D．地方行政法规E．行业标准《药品管理法》属于何种层级的法律规范

常见疾病的自我药疗须知A、1日B、2日C、3日D、5日E、7日治疗荨麻疹使用抗过敏药不宜超过

在渗透系数大、地下水量大的土层中，适宜采用的降水形式为()。

在电子商务网站设计过程中，颜色搭配、版面布局以及文字图片应用等活动属于()。

下列不属于合规管理的重点内容的是()。

绩效考评数据的分析方法一般有()。(2005年5月四级真题)

班杜拉认为，行为的结果因素就是通常所说的强化，并把强化分为()。

在结构化设计方法中，下面哪一项不属于软件设计阶段任务的是()。

下面我要给大家介绍一个相机储存的小窍门。