面试算法题:已知一个数组,数组中两个数之和为N,求两个数在数组中的下标
面试算法题:已知一个数组,数组中两个数之和为N,求两个数在数组中的下标
Tumbler康 发表于10个月前
面试算法题:已知一个数组,数组中两个数之和为N,求两个数在数组中的下标
  • 发表于 10个月前
  • 阅读 7
  • 收藏 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 + ")");
    }
}
共有 人打赏支持
粉丝 2
博文 5
码字总数 11316
×
Tumbler康
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: