建立哈希表的算法（哈希表和排序算法的应用）

建立哈希表的算法（哈希表和排序算法的应用）三数之和运行结果解法三：利用 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%的用户

总结：

两种思路：

• 一种是充分利用基础排序算法的结果（两数之和：初始化头尾两指针，分别向中间移动，一次遍历获取结果）
• 一种是利用Hash Map（或Set）数据结构中查找元素的O(1)复杂度（key为数字或者数字之和，value为位置index）

注意：一个小技巧是，可以预先检查目标之和是否存在，如果不存在，立马返回，将后面的算法“短路”