文档章节

面试算法题:已知一个数组,数组中两个数之和为N,求两个数在数组中的下标

Tumbler康
 Tumbler康
发布于 2017/04/06 12:26
字数 1016
阅读 9
收藏 0
点赞 0
评论 0

如题是最近面试时遇到的,初看这题很简单,于是用下面最简单,也是最笨的方法随手写了下: 直接上代码,思路看注释。

import java.util.*;

/**
 * @author kangyj
 * @version 1.0
 * @desc 算法测试类
 * @createTime 2017/4/5 16:10
 */
public class Test {

    public static void main(String[] args) {

        // 定义数组
        int[] arrays = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int num1 = 0;
        int num2 = 0;
        int result = 0;
        // 接收控制台输入
        Scanner sc = new Scanner(System.in);
        int sum = sc.nextInt();
        // 用于判断结果,跳出最外层循环
        boolean success = false;
        for (int i = 0; i < arrays.length; i++) {
            num1 = arrays[i];
            for (int j = 0; j < arrays.length; j++) {
                if (i == j) {
                    continue;
                }
                num2 = arrays[j];
                // 两数相加,和控制台输入的数字对比。结果相等跳出内层循环
                result = num1 + num2;
                if (result == sum) {
                    System.out.println("------Test.main()------num1:index--=" + i + "num2:index--" + j);
                    success = true;
                    break;
                }
            }
            // 跳出外层循环
            if (success) {
                break;
            }
        }
    }
}

上面的方法时间复杂度(时间复杂度解释,【转】)太高,如果数组中有1w个数字,并且符合条件的数字是最后两个,那需要的时间可想而知……面试时想了半天也没想出其他办法(只能怪自己平时对算法不重视!)。
回来路上一直在各种google,终于找到了简单方法,思路是:
循环遍历数组,将数组元素放入map中。key:数组元素,value:元素下标。(如果有重复元素则不建议这样。后面对重复数组有其他解决办法。)
然后对数组进行排序,然后遍历数组,取第一个数字和最后一个数字相加,如果和大于N,说明其中一个数太大了,可以通过取第二大的数(即倒数第二个数字)来缩小第二个加数;
如果第一个数字和最后一个数字相加,和小于N,说明其中一个数字太小了,可以通过取第二小的数字(即第二个数字)来扩大第一个加数。通过循环遍历,取前面一个数和后面一个数相加,和与N比较。直到和等于N,跳出循环。代码如下:

package com.designer.patterns.algorithm;

import java.util.*;

/**
 * @author kangyj
 * @version 1.0
 * @desc 算法测试类
 * @createTime 2017/4/5 16:10
 */
public class Test {
    public static void main(String[] args) {
        int[] array = {2, 7, 9, 13, 57, 26, 55, 11, 6, 3, 89, 75, 36, 76, 95, 98, 101, 320, 520, 85, 62, 49, 96, 1 };
        int[] array1 = array.clone();
        Map<Integer, Integer> map = new HashMap<>();
        System.out.println("------Test.main()------排序前");
        for (int i = 0; i < array.length; i++) {
            map.put(array[i], i);
            System.out.print(array[i] + ",");
        }
        // 排序
        Arrays.sort(array);

        System.out.println("");
        // 打印排序后的数组
        System.out.println("------Test.main()------排序后");
        for (int i : array) {
            System.out.print(i + ",");
        }
        System.out.println("");

        // 获取控制台用户输入
        Scanner sc = new Scanner(System.in);
        int sum = sc.nextInt();
        int i = 0;
        int j = array.length -1;    // 下标从0开始,最后一个数的下标,应该是长度-1
        int result;
        // 如果两个数之和大于sum,说明第一个大的数太大了,需要缩小,则取第二大的数。如果小于sum,说明第一个小的数小了,需要扩大,则取第二小的数
        while ((result = array[i] + array[j] - sum) !=0 && i < j) {
            if (result > 0) {
                j--;
            } else {
                i++;
            }
        }
    // 当i == j,则没有结果
        if (i == j) {
            System.out.println("------Test.main()------没有结果");
            return;
        }

        // **如果数字不重复**,可以通过map.get(key);获得在原数组中的下标。通过i、j只能取出符合条件的数字在排序后的数组中的位置。
        System.out.println("排序后数组中位置:(" + array[i] + ",下标:" + i + ");(" + array[j] + ",下标:" + j + ")");
        System.out.println("排序前数组中位置:(" + array[i] + ",下标:" + map.get(array[i]) + ");(" + array[j] + ",下标:" + map.get(array[j]) + ")");

        // **如果有重复**,可以通过遍历原数组,和符合条件的数字对比,取其下标,即为数字在原数组中的位置。
//      // 找到第一次数字出现的位置后,可以为s1、s2赋值,跳出循环。
        int s1=-1,s2=-1;
        for(int k=0;k<array1.length-1;k++){
            if(array1[k]==array[i] && s1<0){
                s1=k;
            }
            if(array1[k]==array[j] && s2<0){
                s2=k;
            }
            if(s1>=0 && s2>=0)
            {
                break;
            }
        }
        System.out.println("原数组中位置:(" + array[i] + ",下标:" + s1 +");" + "(" + array[j] + ",下标:" + s2 + ")");
    }
}

© 著作权归作者所有

共有 人打赏支持
Tumbler康
粉丝 2
博文 5
码字总数 11316
作品 0
北京
后端工程师
面试算法知识梳理(14) - 数字算法

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 面试算法知识梳理(2) - 字符串算法第一部分 面试算法知识梳理(3) - 字符串算法第二部分 面试算法知识梳理(4) - 数组第一部分 面试...

泽毛 ⋅ 2017/12/28 ⋅ 0

找出数组中两数之和为指定值的所有整数对

一,问题描述 给定一个整型数组(数组中的元素可重复),以及一个指定的值。打印出数组中两数之和为指定值的 所有整数对 思路1:可以用hash表来存储数组中的元素,这样我们取得一个数后,去判...

一贱书生 ⋅ 2016/11/28 ⋅ 0

Android 面试文档分享

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

泽毛 ⋅ 2017/11/10 ⋅ 0

各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。 ⋅ 2017/12/04 ⋅ 0

某公司的笔试编程题

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

装置图 ⋅ 2016/09/26 ⋅ 0

微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai ⋅ 2012/08/05 ⋅ 0

(转)十月百度,阿里巴巴,迅雷搜狗最新面试七十题

(转)十月百度,阿里巴巴,迅雷搜狗最新面试十一题 来自:http://blog.csdn.net/vjulyv/article/details/6855788 引言 当即早已进入10月份,十一过后,招聘,笔试,面试,求职渐趋火热。而在这...

idea_biu ⋅ 2011/10/20 ⋅ 1

算法面试题总结

1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 16 转换成...

笨笨熊 ⋅ 2011/03/13 ⋅ 0

数据结构与算法面试题80道

1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 16 转换成...

_子墨 ⋅ 2014/10/22 ⋅ 0

一些面试题,整理自网络

腾讯面试题:tcp三次握手的过程,accept发生在三次握手哪个阶段? 答accept发生在三次握手之后。 第一次握手:客户端发送syn包(syn=j)到服务器。 第二次握手:服务器收到syn包,必须确认客户...

waveer ⋅ 2016/12/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 7

mysql in action / alter table

change character set ALTER SCHEMA `employees` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci ;ALTER TABLE `employees`.`t2` CHARACTER SET = utf8mb4 , COLLAT......

qwfys ⋅ 今天 ⋅ 0

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

easyui学习笔记

EasyUI常用控件禁用方法 combobox $("#id").combobox({ disabled: true }); ----- $("#id").combobox({ disabled: false}); validatebox $("#id").attr("readonly", true); ----- $("#id").r......

miaojiangmin ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部