`

【100题】第十四题(数组中找两个数使其和等于输入数)

 
阅读更多

一,题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

二,题目难点在于时间复杂度控制在O(n)

三,方法一

1,分别从数组前,数组后向中间查找。直到前后相遇!!

2,当前得到currentSum>sum说明:大的数太大(数组递增,后面的数太大)。应该将指向最后的标记向前挪动

3,当前得到currentSum<sum说明:大的数太小(数组递增,前面的数太小)。应该将指向最后的标记向后挪动

4,当前得到currentSum=sum说明:找到答案


方法二:假如

1,数组为:a={1、 2、 4、7、11、15 }

2,输入sum=15

3,用15减去a数组中每一个元素得到

b={14、13、11、8、4、0 }

4,a数组向右扫描

b数组向左扫描

5,如果a出现了和b一样的数,稍加判断,就能找出这俩个数来了。



分享到:
评论

相关推荐

    C语言数组练编程习题

    本题目要求将一个用户输入的十进制数转换为其对应的二进制表示,并存储在一个数组中。 **代码解析:** 1. **读取输入:** 读取用户输入的十进制数。 ```c printf("请输入一个十进制数\n"); scanf("%d", &decimal...

    编写数组函数程序

    其基本思想是将数组分为两半,然后比较中间元素与目标值,根据比较结果缩小搜索范围,直到找到目标元素或确定元素不存在。 以下是对程序中关键部分的详细解释: 1. 定义数组s: ```c int s[15]={0,1,2,3,4,5,6,7...

    汇编语言 20个练习题目 代码加实验报告

    5.6 编写程序,将一个包含有20个数据的数组M分成两个数组:正数数组P和负数数组N,并分别把这两个数组中的数据的个数显示出来。 5.7 试编制一个汇编语言程序,求出首地址为DATA的100D字数组中的最小偶数,并把它放在...

    字符串 数组、字母和ASCII值应用

    十三、求两个数的最大公约数 =========================================== =========================================== 输出: Test1:比较两个字符串的大小,如: Test2:二维数组获取每一列的最小值...

    输入一位三位数,让它们分别显示百位数和十位数和个位数

    这段代码通过一系列的除法和取余运算,成功地将输入的数字n分解成了百位、十位与个位三个独立的部分,并存储到了数组a中对应的位置。 #### 2. 输出原始数字及各个位数 ```c printf("the original num:\n"); for (i ...

    数组基础题目作业大纲.doc

    斐波那契数列的每个数是前两个数的和。我们可以用一维数组存储每个月的兔子数量,根据斐波那契数列的规律填充数组,然后输出结果。 通过这些数组基础题目,学生可以更好地理解数组的性质和操作,为更复杂的编程任务...

    上海电机学院C语言实训答案

    (提示: 插入法排序的思路是:先对数组的头两个元素进行排序, 然后根据前两个元素的情况插入第三个元素,再插入第四个元素…)。 (15)爱因斯坦数学题。爱因斯坦曾出过这样一道数学题:有一条长阶梯,若每步跨2...

    javascript入门笔记

    1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...

    Python基础练习题100例(Python3.x).pdf

    在这个Python基础练习题100例中,我们看到三个具体的题目,分别涉及数组操作、数学计算和逻辑推理。 第一题是关于数字排列的问题。题目要求使用1、2、3、4这四个数字组成互不相同且无重复数字的三位数,并打印所有...

    C++蛇形数组(数字倒三角)

    "蛇形数组(数字倒三角)"是一种特殊的矩阵排列方式,通常出现在算法竞赛或编程练习中,例如重庆大学ACM竞赛中的第一题。这个题目要求使用C++编程语言,将数字按照特定的“蛇形”路径填充到一个二维数组中,并将结果...

    第7章 数组-8数组的其他应用——文曲星猜数游戏1

    在这个游戏中,使用了两个数组:`a` 和 `b`。数组 `a` 用于存储计算机生成的四位数,而数组 `b` 则用于存储玩家输入的猜测值。为了确保生成的数字是四位且每位数字不同,有两种方法可以实现: 1. 使用循环和条件...

    求数列中的第1~k小元素

    设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题,这里k不是常量,即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。 2. 具体要求 输入的第一行是一个正整数m,表示测试...

    C语言题库:常见的50道上级题

    1. 数组和循环:在第一题中,使用了数组`a[M]`存储用户输入的n个数,并通过两个for循环找出数组中的最大值和最小值。这是对数组操作和循环控制的基本应用。 2. 阶乘函数与条件判断:第二题中,定义了一个名为`fab`...

    第十四届蓝桥杯 Java C组省赛真题

    本资源为第十四届蓝桥杯 Java C 组省赛真题,涵盖了 Java 编程基础知识点,包括结果填空和程序设计两种题型。本总结将对题目中的知识点进行详细说明。 一、结果填空题 结果填空题要求选手根据题目描述直接填写结果...

    将两个多位十进制数相加,要求加数和被加数均以ASCII码形式各自顺序存放以DATA1和DATA2为首的5个内存单元中(低位在前),结果送回DATA1处

    根据给定文件的信息,本文将详细解析如何在汇编语言环境下实现两个多位十进制数的相加操作。本例中的关键在于理解ASCII码表示的十进制数、加法运算以及结果的处理。 ### 一、问题背景 在计算机编程中,经常需要对...

    _第14届蓝桥杯C++省赛(初级)真题及解析.pdf

    从给定的文件信息来看,主要涉及到了第14届蓝桥杯C++省赛(初级)的一些真题及其解析。接下来,我们将针对文件中提到的几个知识点进行详细阐述。 ### 完全二叉树的高度 **问题描述:** 设只含根结点的二叉树高度为...

    2012年计算机二级VB数组和自定义类型练习题及答案.docx

    1. **定义过程:**在Form2中定义了过程 `Sub aaa(x, y, z)` 用于计算两个数的平方和,在Module1中定义了过程 `Sub bbb(x, y, z)` 用于计算两个数的立方和。 2. **过程调用:**在Form1的命令按钮Click事件中调用这两...

    C++期末复习题库.pdf

    - 题库中的“friend float max(point& a, point& b)”表示一个友元函数,用于重载max函数,以便比较两个Point对象的大小。 8. 模板 - “template&lt;class T&gt; class f{}”表示定义了一个模板类,模板类可以用来创建...

    c语言试题100道.pdf

    14. 第十四个试题要求编写一个简单的计算器程序,要求根据用户从键盘输入的表达式,计算并输出结果。这个试题考察了C语言的表达式计算和函数使用。 15. 第十五个试题要求使用时间函数编写一个猜数程序。这个试题...

    求2n个数的中位数

    - 如果当前两个数组区间的长度都为2,则可以确定中位数为这两个区间内较大的数和较小的数。 - 如果`X[aMid] [bMid]`,那么可以断言中位数不会出现在`X`的前半部分或`Y`的后半部分,因此更新`aLeft = aMid`和`...

Global site tag (gtag.js) - Google Analytics