一、最长一连序列
题目链接：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
给定一个未排序的整数数组 nums ，找出数字一连的最长序列（不要求序列元素在原数组中一连）的长度。
请你筹划并实现时间复杂度为 O(n) 的算法办理此问题。
办理方案：hash法
思路
- 起首，将数组中的元素通过 Arrays.stream(nums).boxed().collect(Collectors.toSet()) 转化为 Set。这是为了快速判断某个数是否存在于集合中，Set 的查找时间复杂度是 O(1)，比利用数组更高效。
- 对 Set 中的每一个元素举行遍历，判断该元素是否大概是某个一连序列的起点。这一点通过查抄 s-1 是否存在来实现。如果 s-1 存在，那么 s 不能作为序列的起点，由于它是某个更长序列的一部分。这样呢可以快速定位到起点元素，提高计算服从，否则还必要内部再遍历匹配，时间复杂度会达到O(n^2)
- 如果 s 是某个序列的起点（即 s-1 不存在），那么从 s 开始，通过 while 循环依次查找 s+1, s+2, … 是否存在，直到序列断开。这个过程会统计当前序列的长度。
- 在每次找到一个序列时，比力其长度与当前记录的最长序列长度 longestLength，更新最长长度并在循环竣事后返回。
- public static int longestConsecutive(int[] nums) {
- Set<Integer> sets = Arrays.stream(nums).boxed().collect(Collectors.toSet());
- int longestLength = 0;
- for (Integer s : sets) {
- // 这里之所以排除s-1的是因为如果存在连续数字，我们肯定是从它的最开始的时候开始计算效率最高
- // 否则还需要内部再遍历匹配，时间复杂度O(n^2)
- if (!sets.contains(s - 1)) {
- int currentNum = s;
- int currentLength = 1;
- while (sets.contains(currentNum + 1)) {
- currentNum++;
- currentLength++;
- }
- longestLength = Math.max(longestLength, currentLength);
- }
- }
- return longestLength;
- }
哈希表是一种常用于办理查找、判断或频率统计类问题的数据结构。它的重要上风是查找、插入和删除操纵的时间复杂度为 O(1)，这使得它特别适合处理惩罚必要快速查找和频率统计的问题。
1. 两数之和
- 问题描述：给定一个数组和一个目的值，找出数组中两数之和为目的值的两个数字的索引。
- 哈希法思路：
- 通过哈希表存储已经遍历过的数字及其索引。
- 每次遍历当前数字时，查抄当前数字的补数是否已经在哈希表中，如果存在，则说明找到了匹配的两数之和。
- 为何用哈希表：题目必要在 O(1) 时间内判断一个数的补数是否已经出现过，哈希表的快速查找特性完美满意这种需求。
2. 字母异位词分组
- 问题描述：给定一组字符串，将它们按照字母异位词分组。
- 哈希法思路：
- 遍历字符串数组，将每个字符串排序后作为键，存储在哈希表中，值为该键对应的所有异位词的列表。
- 遍历竣事后，哈希表的每个键值对即为一组异位词。
- 为何用哈希表：异位词有一个共同点，即它们颠末排序后是类似的。哈希表可以用来快速归类类似“特性”的字符串。(也可以将字符串出现次数作为唯一特性键)
3. 最长一连序列（Longest Consecutive Sequence）
- 问题描述：给定一个未排序的整数数组，找出最长一连序列，并且要求算法的时间复杂度为O(n)。
- 哈希法思路：
- 先把所有数字存入哈希表，然后再遍历这些数字。
- 对于每个数字，判断其前一个数字是否在哈希表中，如果不在，则认为该数字是一个序列的起点，然后依次寻找后续的一连数字。
- 通过哈希表，我们可以在 O(1) 时间内判断某个数字是否存在，从而使得整个过程可以在线性时间内完成。
- 为何用哈希表：题目要求在 O(n) 时间内完成查找，哈希表能够在 O(1) 时间内判断一个数字是否存在，有效支持一连序列的查找。
总体总结：哈希法的应用思路
哈希表的焦点上风是快速查找和常数时间的操纵，当算法问题涉及到以下场景时，通常可以考虑哈希表：
- 频繁查找元素是否存在： 当题目要求快速确定某个值是否已经存在于集合中，哈希表是非常适合的。
- 快速查找某种关系匹配： 比如“找到符合某种和、差、乘积等条件的两个数”，这类问题通常可以利用哈希表举行配对。
- 数据归类或分组：如果必要根据某种特性（比如字符串的排序形式、数字的特定属性等）来分组，哈希表可以用来高效管理和存储这些特性与对应的对象集合。焦点思路就是我们说的去找到唯一的键，通过其举行分组！
- 高效去重和统计： 如果题目必要对数据举行去重或频次统计，哈希表可以帮助你在遍历过程中以常数时间完成这些操纵。
在你思考如何优化暴力解法时，如果问题具有匹配查找、快速判断存在性或归类的特点，往往能快速联想到哈希表。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
