文档章节

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

Tumbler康
 Tumbler康
发布于 2017/04/06 12:26
字数 1016
阅读 9
收藏 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
0
找出数组中两数之和为指定值的所有整数对

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

一贱书生
2016/11/28
35
0
某公司的笔试编程题

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

装置图
2016/09/26
0
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

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

云栖希望。
2017/12/04
0
0
Android 面试文档分享

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

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

sourcetree 离线免注册登录安装教程

Sourcetree是一个优秀的git可视化管理工具,深受开发者喜爱Sourcetree官网,但是在安装时需要谷歌账户登录,需要翻qiang才可以,此一点一直被人们所诟病。今天本教程就为大家提供离线免登陆安...

QQZZFT
10分钟前
0
0
使用 PostgreSQL 解决一个实际的统计分析问题

使用 PostgreSQL 解决一个实际的统计分析问题作者:老农民(刘启华)Email: 46715422@qq.com 之前有个朋友扔给我一个奇葩需求,他们公司之前做了一批问卷调查,全部都是统一格式的excel...

新疆老农民
13分钟前
0
0
TypeScript基础入门之高级类型的映射类型

转发 TypeScript基础入门之高级类型的映射类型 高级类型 映射类型 一个常见的任务是将一个已知的类型每个属性都变为可选的: interface PersonPartial {    name?: string;    age?...

durban
28分钟前
0
0
Dubbo源码分析(6):Dubbo内核实现之基于SPI思想Dubbo内核实现

SPI接口定义 定义了@SPI注解 package com.alibaba.dubbo.common.extension; import java.lang.annotation.Documented;import java.lang.annotation.ElementType;import java.lang.an......

郑加威
29分钟前
0
0
RxJS的另外四种实现方式(后记)—— 同时实现管道和链式编程

目录 RxJS的另外四种实现方式(序) RxJS的另外四种实现方式(一)——代码最小的库 RxJS的另外四种实现方式(二)——代码最小的库(续) RxJS的另外四种实现方式(三)——性能最高的库 Rx...

一个灰
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部