Java查找不重复无序数组中是否存在两个数字的和为某个值

2024-10-21 02:32:38

今天去某在线教育面试面试官让做的一道题，题目描述如下：

给定一个不重复的无序数组arr和一个定值num
查找arr中是否有两个数的和等于num
有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回null

很多人一想可能就是两层for循环，我想了很久最后写了双重for循环…【这个代码太easy就不放了】然后面试官说知道哈希吗，由于哈希查找的时间复杂度是O(1)，从哈希的角度去考虑，这中间还有一堆就不描述了，说一下怎么用哈希实现。

实现思路：

将数组中的所有的值放入HashMap的Key中，Value存放该值对应的下标，遍历这个HashMap，取得Key，计算如果可以和这个Key加起来的和为num的值，如果这个值存在，就直接返回这两个下标。遍历一次的时间复杂度为O(N)，查找的时间复杂度是O(1)，总体时间复杂度O(N)。

代码实现：

public class getTwoNumsSumEquals {
  public static void main(String[] args) {
    int[] arr = new int[]{3, 4, 6, 5, 9, 8};
    int num = 8;
    int[] ret = getIndex(arr, num);
    System.out.println("index of two numbers R:" + ret[0] + " " + ret[1]);
  }
  // 找到这两个数的下标并返回（以长度为2的数组的形式返回）
  private static int[] getIndex(int[] arr, int num) {
    int[] ret = new int[2];
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    int index = 0;
    // 将每个数字和其下标放进map中
    for (Integer curr : arr) {
      hashMap.put(curr, index++);
    }
   // 遍历HashMap并判断
    for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
      int value = entry.getKey();
      int subValue = num - value;
      if(hashMap.containsKey(subValue)) {
        // 找到啦!
        ret[0] = entry.getValue();
        ret[1] = hashMap.get(subValue);
        break;
      }
    }
    return ret;
  }
}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

面试题:Java 实现查找旋转数组的最小数字

在算法面试中,面试官总是喜欢围绕链表.排序.二叉树.二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流.而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序员.所以学会数学建模和分析问题,并用合理的算法或数据结构来解决问题相当重要. 面试题:打印出旋转数组的最小数字题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该
Java数组高级算法与Arrays类常见操作小结【排序、查找】

本文实例讲述了Java数组高级算法与Arrays类常见操作.分享给大家供大家参考,具体如下: 冒泡排序冒泡排序原理冒泡排序代码: package cn.itcast_01; /* * 数组排序之冒泡排序: * 相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处 */ public class ArrayDemo { public static void main(String[] args) { // 定义一个数组 int[] arr = { 24, 69, 80, 57,
Java对数组实现选择排序算法的实例详解

一. 算法描述选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟
Java数组常用排序算法实例小结

本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo
简单讲解奇偶排序算法及在Java数组中的实现

奇偶排序是一个比较有个性的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序举例吧, 待排数组 [6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较 [2 1 6 4 5 9] 交
Java算法实现调整数组顺序使奇数位于偶数之前的讲解

调整数组顺序使奇数位于偶数之前 1. 题目描述输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 2. 题目分析该题目类似于一个选择排序,将奇数选择出来,放置于数据前面的位置,保持其他未被选择的元素的相对位置不变: 1. 遍历数组,当数组元素为奇数是进行处理,判断条件为 n % 2 != 0 2. 设置一个变量标注当前已遍历的元素中奇数的个数oddNum,也是将该奇数元素
详解Java数据结构和算法（有序数组和二分查找）

一.概述有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点优点:查找速度比无序数组快多了缺点:插入时要按排序方式把后面的数据进行移动三.有序数组和无序数组共同优缺点删除数据时必须把后面的数据向前移动来填补删除项的漏洞四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组赋值默
java实现二分法查找出数组重复数字

本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下 package offer; /** * 二分查找的思想来找到数组中重复的数字,时间复杂度在o(nlogn)-o(n^2) */ public class FindDuplicate3 { public static void main(String[] args) { int numbers[] = {0,1,2,3,4,4,6,7};//数组中的数大小从0 到 numbers.length-1 f
Java查找不重复无序数组中是否存在两个数字的和为某个值

今天去某在线教育面试面试官让做的一道题,题目描述如下: 给定一个不重复的无序数组arr和一个定值num 查找arr中是否有两个数的和等于num 有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回null 很多人一想可能就是两层for循环,我想了很久最后写了双重for循环-[这个代码太easy就不放了]然后面试官说知道哈希吗,由于哈希查找的时间复杂度是O(1),从哈希的角度去考虑,这中间还有一堆就不描述了,说一下怎么用哈希实现. 实现思路: 将数组中的所有的值放入HashMap的K
Java C++解决在排序数组中查找数字出现次数问题

目录 1.题目 2.思路 3.c++代码 4.java代码 1.题目统计一个数字在排序数组中出现的次数. 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 提示: 0 <= nums.length <= 10^5 -10^9 <= nums[i] <= 10^9 nums 是一个非递减数组 -10^9 <= target &l
C++算法之在无序数组中选择第k小个数的实现方法

本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in
python 实现在无序数组中找到中位数方法

一.问题描述 1.求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置.要求:不能使用排序,时间复杂度尽量低 2.例如: lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5 lists = [3, 1, 2] , 中位数为 2 3.算法思想: 利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数
php实现数组中出现次数超过一半的数字的统计方法

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.如果不存在则输出0. 两种方式: 1.定义一个新数组arr,遍历数组给arr赋值,arr[元素]=出现的次数 2.排序下arr,取第一个的key和value,key是目标元素,value是出现次数,验证下后返回 3.时间复杂度是O(n) 空间上会新创建个数组 1.定义变量e代表出现次数最多的元素,变量coun
JavaScript实现找出数组中最长的连续数字序列

原始题目: 给定一个无序的整数序列, 找最长的连续数字序列. 例如: 给定[100, 4, 200, 1, 3, 2], 最长的连续数字序列是[1, 2, 3, 4]. 小菜给出的解法: function maxSequence(array,step){ var _array = array.slice(), //clone array _step = 1, _arrayTemp = [], i = 0; var parseLogic = { //result container parseRe
如何高效率去掉js数组中的重复项

方式一: 常规模式 1.构建一个新的临时数组存放结果 2.for循环中每次从原数组中取出一个元素,用这个元素循环与临时数组对比 3.若临时数组中没有该元素,则存到临时数组中方式二: 使用了默认Js数组sort默认排序,是按ASCII进行排序: 若要按照升降序的排列如下:<控制台打印输出> 1.先将当前数组进行排序 2.检查当前中的第i个元素与临时数组中的最后一个元素是否相同,因为已经排序,所以重复元素会在相邻位置 3.如果不相同,则将该元素存入结果数组中方式三: <推荐>利
根据key删除数组中指定的元素实现方法

php数组中元素的存在方式是以键值对的方式('key'=>'value'),有时候我们需要根据键删除数组中指定的某个元素. function bykey_reitem($arr, $key){ if(!array_key_exists($key, $arr)){ return $arr; } $keys = array_keys($arr); $index = array_search($key, $keys); if($index !== FALSE){ array_splice($arr,
Python实现找出数组中第2大数字的方法示例

本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis
PHP根据key删除数组中指定的元素

php数组中元素的存在方式是以键值对的方式('key'=>'value'),有时候我们需要根据键删除数组中指定的某个元素. function bykey_reitem($arr, $key){ if(!array_key_exists($key, $arr)){ return $arr; } $keys = array_keys($arr); $index = array_search($key, $keys); if($index !== FALSE){ array_splice($arr,

Java查找不重复无序数组中是否存在两个数字的和为某个值

相关推荐

随机推荐