时间：2020-10-15 23:15:40 | 栏目：JAVA代码 | 点击：次
今天去某在线教育面试面试官让做的一道题，题目描述如下：
很多人一想可能就是两层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;
}
}
总结