文档章节

IT公司100题-14-排序数组中和为给定值的两个数字

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/12/15 13:41
字数 253
阅读 119
收藏 2

问题描述:

输入一个升序排序的数组,给定一个目标值target,求数组的两个数a和b,a+b=target。如果有多个组合满足这个条件,输出任意一对即可。

例如,输入升序数组【1, 3, 4, 5, 13, 17】和目标值20。输出3和17。

分析:

最简单的办法,直接遍历,时间复杂度为O(n^2)。

双下标法:low和high

a[low]+a[high] < target, low++;

a[low]+a[high] > target, high–;

a[low]+a[high] == target, return low and high;

代码实现如下所示:

package oschina.IT100;

/**
 * @project: oschina
 * @filename: IT13.java
 * @version: 0.10
 * @author: JM Han
 * @date: 12:08 PM 12/15/2015
 * @comment: find two number in an incredent list whose sum is given
 * @result:
 */

public class IT13 {
   public static boolean findTwo(int[] arr, int sum){
      int i = 0;
      int j = arr.length - 1;
      boolean flag = true;
      while(flag && (i < j)){
         if((arr[i] + arr[j]) < sum){
            i++;
         } else if ((arr[i] + arr[j]) > sum){
            j--;
         } else{
            System.out.println("i: " + i + " j: " + j);
            flag = false;
         }
      }
      return flag;
   }

   public static void main(String[] args) {
      int[] array = {1,3,4,5,13,17,18};
      findTwo(array, 25);
   }
}


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
leetcode|初级算法-数组

01 起 最近“不务正业地”刷了一波leetcode上的算法题,初级算法已经刷完50%,战况如下, 刷题固然爽快,但及时总结才是进步之道,下面就数组部分的题目进行回顾和总结。 注意,刷题使用的语...

邓莎
2018/09/05
0
0
Leetcode Solutions(一) two-sum - 知乎

Leetcode Solutions(一) two-sum 题目 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 解题思路 ...

萌新的学习日记
前天
0
0
某公司的笔试编程题

原题:     给定一个数组candidate和一个目标值target,求出candidate中两个数的和等于target的组合。比如输入数组[1,2,3,4,7]和目标值10.输出[ 3, 7]如果找不到输出[ -1,-1 ]。要求时间复...

装置图
2016/09/26
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
编程题——11~20

十一、数值的整数次方 实现函数double Power( double base, int exponent ),求base的exponent。不使用哭函数,同时 不需要考虑大数问题。 十二、打印1到最大的n位数 输入数字n,按顺序打印出...

thanatos_y
2016/07/21
16
0

没有更多内容

加载失败,请刷新页面

加载更多

网站安全维护公司对渗透测试php后门分析

很多想做渗透测试的朋友都想了解关于PHP后门漏洞的安全测试重点方法,以及该如何预防被中php后门,本节由我们的Sine安全高级渗透工程师进行全面的讲解,来让大家更好的理解和了解php代码的安全...

网站安全
9分钟前
2
0
在github上创建代码仓库时忘记添加.gitignore文件或修改了.gitignore该怎么办?

#清除本地缓存(改变成未track状态) #git rm -r --cached . 表示清除项目中所有文件的本地缓存 git rm -r --cached xxx #xxx表示不想版本控制的文件,比如小编可以输入test.o #.gitignore中的...

博爱飞扬
9分钟前
3
0
Fsimage 与 EditLog定义及合并过程

有很多客户端在向 hdfs 中写数据,同时有很多客户端在查数据,这就涉及到一个响应速度问题。因为只有一个 namenode ,客户端在写的时候,必须迅速记下来。 1. 向 namenode 询问可以存储到哪些...

Garphy
13分钟前
4
0
TI KeyStone C66x开发板处理器、NAND FLASH、NOR FLASH

TL6678F-EasyEVM是广州创龙基于SOM-TL6678F核心板而研发的一款多核高性能DSP+FPGA开发板。开发板采用核心板+底板方式,底板采用沉金无铅工艺的8层板设计,尺寸为247.33mm*139.8mm,它为用户提...

Tronlong创龙
31分钟前
5
0
【2019年8月版本】OCP 071认证考试最新版本的考试原题-第13题

Choose the best answer. Examine this query: SELECT TRUNC (ROUND(156.00,-2),-1) FROM DUAL; What is the result? A) 16 B) 160 C) 150 D) 200 E) 100 Answer:D (解析:关键就是 round ......

oschina_5359
41分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部