建立哈希表的算法(哈希表和排序算法的应用)三数之和运行结果解法三:利用 Map数据结构,复杂度为O(N)算法分析:利用Hash Map最优,一次遍历即可完成code
刷leetcode过程中,会遇到两数之和、三数之和、四数之和、N数之和的求解,这里做个简单总结。
两数之和
解法一:暴力搜索,复杂度为O(N^2)
解法二:利用基础的排序算法,复杂度为O(NlogN) O(N)=O(NlogN)
解法三:利用 Map数据结构,复杂度为O(N)
算法分析:利用Hash Map最优,一次遍历即可完成
code
运行结果
三数之和
解法一:暴力搜索,O(N^3)
解法二:利用基础的排序算法,复杂度为O(NlogN) O(N^2)=O(N^2),相对两数之和,外套一层for循环
解法三:利用 Map数据结构,复杂度为O(N^2),将三数之和拆分成单数、两数之和
算法分析:利用排序算法效果常数项小,效果最好
code
运行结果
四数之和、任意数之和
这里用Leetcode原题:
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a b c d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
解法一:利用排序,递归实现任意数之和nSum
解法二:拆分成两个"两数之和",将"两数之和"的思路扩展,时间上击败97%的用户
总结:
两种思路:
注意:一个小技巧是,可以预先检查目标之和是否存在,如果不存在,立马返回,将后面的算法“短路”