【转】 http://zhedahht.blog.163.com/blog/static/2541117420072143251809/
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。
分析:如果我们不考虑时间复杂度,最简单想法的莫过去先在数组中固定一个数字,再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。
我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字,那太好了,我们找到了要找的两个数字;如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们是不是可以把较小的数字的往后面移动一个数字?因为排在后面的数字要大一些,那么两个数字的和也要大一些,就有可能等于输入的数字了;同样,当两个数字的和大于输入的数字的时候,我们把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。
我们把前面的思路整理一下:最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。
问题是这样的思路是不是正确的呢?这需要严格的数学证明。感兴趣的读者可以自行证明一下。
参考代码:
///////////////////////////////////////////////////////////////////////
// Find two numbers with a sum in a sorted array
// Output: ture is found such two numbers, otherwise false
///////////////////////////////////////////////////////////////////////
bool FindTwoNumbersWithSum
(
int data[], // a sorted array
unsigned int length, // the length of the sorted array
int sum, // the sum
int& num1, // the first number, output
int& num2 // the second number, output
)
{
bool found = false;
if(length < 1)
return found;
int ahead = length - 1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
// if the sum of two numbers is equal to the input
// we have found them
if(curSum == sum)
{
num1 = data[behind];
num2 = data[ahead];
found = true;
break;
}
// if the sum of two numbers is greater than the input
// decrease the greater number
else if(curSum > sum)
ahead --;
// if the sum of two numbers is less than the input
// increase the less number
else
behind ++;
}
return found;
}
分享到:
相关推荐
LeetCode 问题 34 要求在一个增序的整数数组中找出给定目标值的开始和结束位置。如果数组中不存在目标值,返回 [-1, -1]。这个问题可以通过两次二分查找来解决:一次查找目标值开始的位置,另一次查找结束的位置。 ...
7.2 在排序数组中查找给定值的插入位置 7.3 在二维排序数组中查找给定值 7.4 在旋转有序数组中查找最小值 7.4.1 数组无重复 7.4.2 数组有重复 7.5 在旋转排序数组中查找指定数字 8. 暴力枚举法 8.1 求集合的子集 8.2...
jsSort可以按日期,数字和字符串值排序。 可以通过在属性字符串的开头附加“ [ASC]”或“ [DESC]”来设置每个属性的排序顺序。 如果未指定排序顺序,则默认为升序排序。用法首先使用脚本标签或使用commonJS / AMD...
2、 能够人工输入或随机产生一个长度为 n 的整数数组,要求数组任意两个元素都互不相同; 3、 设计一个算法判断要求 2 中产生的整数数组是否为或未排序(输出 0)、升序(输出 1)、降序(输出 2)、先升后降(输出...
例如,长度为8的线性表关键码序列为:[6,13,27,30,38,46,47,70],被查元素为38,首先将与线性表的中间项比较,即与第4个数据元素30相比较,38大于中间项30的值,则在线性表[38,46,47,70]中继续查找;...
找出两个已排序数组的并集和交集。 数组 编写一个程序,将数组循环旋转一个。 数组查找最大和连续子数组 [V. 输入法] 数组最小化高度之间的最大差异 [V.IMP] 阵列最小数量到达数组末尾的跳转次数 数组在 N+1 整数数...
将正整数x中的每位偶数数字依次取出,并返回a数组下标为偶数的所有元素平均值,并在主函数中输出数组b及返回的平均值,用辗转相除法求两个给定正整数的最大公约数和最小公倍数,用递归的方法求两个数的最大公约数,...
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数 给定一个 32 位有符号整数,将整数中的数字进行反转 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数 给定...
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数 给定一个 32 位有符号整数,将整数中的数字进行反转 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数 给定...
+ 运算符 将两个数字表达式的值相加,或连接两个字符串。 ++ 运算符 变量值加 1。 += 运算符 将表达式的值加到变量中。 , 运算符 使两个表达式按顺序执行。 - 运算符 从一个表达式中减去另一个表达式的值,或对...
将两个排序数组合并为一个排序数组 将数组中的0推到末尾 将数组左旋转给定数量的元素 在数组中查找第二大元素 对仅包含0、1和2的数组进行排序 字符数组和2D数组 在数组中存储两个数字,然后在另一个数组中找到它们...
找出两个已排序数组的并集和交集。 数组 编写一个程序,将数组循环旋转一个。 数组查找最大和连续子数组 [V. 输入法] 数组最小化高度之间的最大差异 [V.IMP] 阵列最小数量到达数组末尾的跳转次数 数组在 N+1 整数数...
从两个链表中计算总和等于给定值的对 链表的归并排序 给定一个由 0、1 和 2 组成的链表,对其进行排序。 合并两个已排序的链表 反转链表 从链表末尾开始的第 N 个节点 将链表表示的两个数字相加 两个链表的交集 从...
+ 运算符 将两个数字表达式的值相加,或连接两个字符串。 ++ 运算符 变量值加 1。 += 运算符 将表达式的值加到变量中。 , 运算符 使两个表达式按顺序执行。 - 运算符 从一个表达式中减去另一个表达式的值,或对...
+ 运算符 将两个数字表达式的值相加,或连接两个字符串。 ++ 运算符 变量值加 1。 += 运算符 将表达式的值加到变量中。 , 运算符 使两个表达式按顺序执行。 - 运算符 从一个表达式中减去另一个表达式的值,或对...
8.1写两个函数,分别求两个整数的最大公约数和最小公倍数,用主函数调用这两个函数,并输出结果,两个整数由键盘输入。 47 8.2 47 8.3写一个判素数的函数,在主函数输入一个整数,输出是否素数的信息。 49 8.4写一...
找出两个已排序数组的并集和交集。 编写一个程序,将数组循环旋转一个。 找到最大和连续子数组 [V. 输入法] 最小化高度之间的最大差异 [V.IMP] 最低数量到达数组末尾的跳转次数 在 N+1 整数数组中查找重复项 在不...
两个已排序数组的中间元素之和 快速排序 归并排序 两个已排序数组的第 K 个元素 回溯: N-皇后问题 解决数独 迷宫问题中的老鼠 字谜 生成 IP 地址 位魔术: 找到第一个设置位 最右边的不同位 检查是否设置了第 K 位 ...
8. 查找数组中的最大值:在给定的数组中找到最大的数,并打印结果。 9. 冒泡排序:对给定的整数数组进行冒泡排序,并打印排序后的结果。 10. 计算圆的面积:根据给定的半径计算圆的面积,并打印结果。 这些例子涵盖...
用npm test arrayShift挑战此函数在排序数组中查找值的索引。 它返回该索引。 如果该值不在数组中,则该函数将返回-1。方法与效率我们找到了数组的中间索引,检查该值是否匹配,大于或小于该索引处的数字。 然后,...