( 双指针算法分类 | 相向双指针 | 有效回文串 )
【算法】双指针算法 ( 有效回文串 II )
【算法】哈希表 ( 两数之和 )
----
文章目录
算法 系列博客
一、两数之和
使用哈希表解决问题..., 找到数组中的两个元素之和 , 等于给定的 target 值 ;
该问题最直观的解法 , 就是 蛮力算法 ;
如 : 给定数组 [6, 4, 2, 9] , 给定 target 值为 10 , 找出数组中哪两个元素之和为..., 外层循环遍历数组元素 , 内层循环遍历 target - 数组元素 值是否在数组中 ;
上述算法事件复杂度为
O(n^2)
;
这里的内层循环中 , 检测一个数字是否在数组中 , 可以使用...哈希表 进行实现 , 哈希表查询的单次操作的时间复杂度是
O(1)
,
n
次查询的操作是
O(n)
;
哈希表在该算法中 , 既不是输入 , 也不是输出 , 是算法计算过程中的耗费 ,..., 哈希表中没有 4 , 但此时将 4=2 键值对 插入了 HashMap , 在之后遍历 4 时 , 肯定能找到索引值 2 ;
按照这种遍历方式 , 如果存在这两个元素 , 总能在
O(n)
时间内找到两个值