【算法】哈希表 ( 两数之和 )
算法 系列博客
【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
文章目录
使用哈希表解决问题 , 一般不需要手动实现哈希表 , 一般使用 HashSet 或 HashMap 即可 ;
一、两数之和
两数之和 : https://www.lintcode.com/problem/56/
给定一个未排序的数组 , 找到数组中的两个元素之和 , 等于给定的 target 值 ;
该问题最直观的解法 , 就是 蛮力算法 ;
如 : 给定数组 6, 4, 2, 9 , 给定 target 值为 10 , 找出数组中哪两个元素之和为 10 ;
如果使用蛮力算法 , 就是遍历所有的数组元素 , 如 遍历 6 , target ( = 10 )减去该被遍历的元素 , 结果是 4 , 然后检测 4 在不在数组中 ;
这样需要设计 两层循环 , 外层循环遍历数组元素 , 内层循环遍历 target - 数组元素 值是否在数组中 ;
上述算法事件复杂度为
;
这里的内层循环中 , 检测一个数字是否在数组中 , 可以使用 哈希表 进行实现 , 哈希表查询的单次操作的时间复杂度是
,
次查询的操作是
;
哈希表在该算法中 , 既不是输入 , 也不是输出 , 是算法计算过程中的耗费 , 因此其空间复杂度是
;
哈希表的 时间复杂度是
, 空间复杂度是
;
哈希表存使用 HashMap 集合体现 ;
设计一个循环 , 遍历数组元素 number ; 遍历时检测 target - number 是否在HashMap中 , 如果不在 , 则加入到哈希表中 ;
将 target - number 的值作为 HashMap 集合的 Key 键 , 将该 number 的索引作为 Value 值 ;
上述操作 , 一边遍历 , 一边将数组元素插入到哈希表中 , 3, 6, 2, 4 , 在遍历到 6 时 , 从哈希表中查找 10 - 6 = 4 这个值 , 哈希表中没有 4 , 但此时将 4=2 键值对 插入了 HashMap , 在之后遍历 4 时 , 肯定能找到索引值 2 ;
按照这种遍历方式 , 如果存在这两个元素 , 总能在
时间内找到两个值
代码示例 :
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 键存放 target - numbers[i], 值存放对应的 i 索引值
// 如果正在遍历的 numbers[j], 恰好等于某个 target - numbers[i]
// 说明 i, j 就是要找的两个索引值
HashMap<Integer, Integer> hashMap = new HashMap<>();
// 要返回的值
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (hashMap.get(numbers[i]) != null) {
// 如果集合中有该值, 说明已经找到了两数之和为 target 的两个元素了, 可以直接返回
result[0] = hashMap.get(numbers[i]);
result[1] = i;
return result;
}
// 向哈希表中存储 target - numbers[i]
hashMap.put(target - numbers[i], i);
}
return result;
}
}
class Main {
public static void main(String[] args) {
System.out.println(
new Solution().twoSum(new int[]{1,2,4,6}, 10)
);
}
}腾讯云开发者
