今天去某在线教育面试面试官让做的一道题，题目描述如下：
很多人一想可能就是两层for循环，我想了很久最后写了双重for循环…【这个代码太easy就不放了】然后面试官说知道哈希吗，由于哈希查找的时间复杂度是o(1)，从哈希的角度去考虑，这中间还有一堆就不描述了，说一下怎么用哈希实现。
实现思路：
将数组中的所有的值放入hashmap的key中，value存放该值对应的下标，遍历这个hashmap，取得key，计算如果可以和这个key加起来的和为num的值，如果这个值存在，就直接返回这两个下标。遍历一次的时间复杂度为o(n)，查找的时间复杂度是o(1)，总体时间复杂度o(n)。
代码实现：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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;
}
}
|
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对快网idc的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/sdr_zd/article/details/82904396
相关文章
猜你喜欢
- ASP.NET自助建站系统的域名绑定与解析教程 2025-06-10
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
