文档章节

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

Tumbler康
 Tumbler康
发布于 2017/04/06 12:26
字数 1016
阅读 11
收藏 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
北京
后端工程师
私信 提问
找出数组中两数之和为指定值的所有整数对

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

一贱书生
2016/11/28
35
0
【算法】LeetCode算法题-Two Sum

程序 = 数据结构 + 算法。 算法是每一位程序员学习成长之路上无法避开的重要一环,并且越早接触越好。今后会每天做些算法题,至少每天做一道题目,同时会记录自己的解题思路和代码,通过【算...

小川94
10/15
0
0
某公司的笔试编程题

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

装置图
2016/09/26
0
0
面试算法知识梳理(14) - 数字算法

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

泽毛
2017/12/28
0
0
Android 面试文档分享

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

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
5
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
17
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
33
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部