文档章节

【九度OJ1352】|【剑指offer41】和为S的两个数字

aqia358
 aqia358
发布于 2013/10/17 16:54
字数 448
阅读 8
收藏 0
点赞 0
评论 0
题目描述:
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输入:
每个测试案例包括两行:
第一行包含一个整数n和k,n表示数组中的元素个数,k表示两数之和。其中1 <= n <= 10^6,k为int
第二行包含n个整数,每个数组均为int类型。
输出:

对应每个测试案例,输出两个数,小的先输出。如果找不到,则输出“-1 -1”

知识点:
已知数组求两数的和为固定值,利用前后两个指针向中间移动,同时判断是否满足所求的值(find2()),可以缩短运行时间(find())

此题,因为是递增数组,所以第一次求出a[low]+a[high]==k,则是乘积最小的那个。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

	public static void find(int[] a,int target){
		int m = 0;
		int n = 0;
		boolean flag = false;
		for(int i = 0; i < a.length; i++){
			for(int j = i+1; j < a.length; j++){
				if(a[i] * 2 > target){
					i = a.length;
					j = a.length;
					break;
				}
				int temp = a[i] + a[j];
				if(temp > target){
					break;
				}else if(temp == target){
					m = a[i];
					n = a[j];
					flag = true;
					i = a.length;
					j = a.length;
					break;
				}
			}
		}
		if(!flag){
			System.out.println("-1 -1");
		}else{
			if(m > n)
				System.out.println(n+" "+m);
			else
				System.out.println(m+" "+n);
		}
			
	}
	public static void find2(int[] a, int target){
		int low = 0;
		int high = a.length -1;
		while(low < high){
			if(a[low] + a[high] == target)break;
			else if(a[low] + a[high] < target)
				low++;
			else
				high--;
		}
		if(low < high)
			System.out.println(a[low]+" "+a[high]);
		else
			System.out.println("-1 -1");
	}
	
	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != st.TT_EOF){
			int n = (int) st.nval;
			st.nextToken();
			int target = (int) st.nval;
			int[] a = new int[n];
			int count = 0;
			while(count < n){
				st.nextToken();
				a[count++] = (int) st.nval;
			}
			find2(a, target);
		}
	}

}



© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
C语言经典算法(二)

C语言作为多数工科学校编程入门的教学工具语言,是很多朋友开启编程世界大门的钥匙。今天,承接上一篇C语言经典算法(一),我继续给大家带来C语言经典算法,欢迎大家与小编多多交流。 六、9...

小辰GG ⋅ 2017/11/28 ⋅ 0

【九度OJ1522】|【剑指offer21】包含min函数的栈

题目描述: 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行为一个整数n(1<=n<=1...

aqia358 ⋅ 2013/12/23 ⋅ 0

C语言经典算法

C语言作为多数工科学校编程入门的教学工具语言,是很多朋友开启编程世界大门的钥匙。今天,承接上一篇C语言经典算法(一),我继续给大家带来C语言经典算法,欢迎大家与小编多多交流。 六、9...

小辰带你看世界 ⋅ 01/04 ⋅ 0

算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

剑指Offer学习总结-二维数组寻找数字

剑指Offer学习总结-二维数组寻找数字 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000 ⋅ 01/15 ⋅ 0

python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905 ⋅ 06/03 ⋅ 0

【九度OJ1348】|【剑指offer36】数组中的逆序对

题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。输入: 每个测试案例包括两行: 第一行包含一个...

aqia358 ⋅ 2014/03/17 ⋅ 0

剑指Offer学习总结-旋转数组的最小数字

剑指Offer学习总结-旋转数组的最小数字 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blo...

wwlcsdn000 ⋅ 01/16 ⋅ 0

*【九度OJ1362】|【剑指offer20】顺时针打印矩阵

题目描述: 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,1...

aqia358 ⋅ 2013/12/25 ⋅ 0

剑指Offer学习总结-重建二叉树

剑指Offer学习总结-重建二叉树 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.co...

wwlcsdn000 ⋅ 01/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 27分钟前 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 59分钟前 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 今天 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 今天 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部