力扣热题100刷题日志(Hash篇下)

打印 上一主题 下一主题

主题 958|帖子 958|积分 2874

一、最长一连序列

题目链接: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,更新最长长度并在循环竣事后返回。
  1. public static int longestConsecutive(int[] nums) {
  2.         Set<Integer> sets = Arrays.stream(nums).boxed().collect(Collectors.toSet());
  3.         int longestLength = 0;
  4.         for (Integer s : sets) {
  5.             // 这里之所以排除s-1的是因为如果存在连续数字,我们肯定是从它的最开始的时候开始计算效率最高
  6.             // 否则还需要内部再遍历匹配,时间复杂度O(n^2)
  7.             if (!sets.contains(s - 1)) {
  8.                 int currentNum = s;
  9.                 int currentLength = 1;
  10.                 while (sets.contains(currentNum + 1)) {
  11.                     currentNum++;
  12.                     currentLength++;
  13.                 }
  14.                 longestLength = Math.max(longestLength, currentLength);
  15.             }
  16.         }
  17.         return longestLength;
  18.     }
复制代码
二、哈希法的总体思路

哈希表是一种常用于办理查找、判断或频率统计类问题的数据结构。它的重要上风是查找、插入和删除操纵的时间复杂度为 O(1),这使得它特别适合处理惩罚必要快速查找和频率统计的问题。
1. 两数之和


  • 问题描述:给定一个数组和一个目的值,找出数组中两数之和为目的值的两个数字的索引。
  • 哈希法思路:

    • 通过哈希表存储已经遍历过的数字及其索引。
    • 每次遍历当前数字时,查抄当前数字的补数是否已经在哈希表中,如果存在,则说明找到了匹配的两数之和。

  • 为何用哈希表:题目必要在 O(1) 时间内判断一个数的补数是否已经出现过,哈希表的快速查找特性完美满意这种需求。
2. 字母异位词分组


  • 问题描述:给定一组字符串,将它们按照字母异位词分组。
  • 哈希法思路:

    • 遍历字符串数组,将每个字符串排序后作为键,存储在哈希表中,值为该键对应的所有异位词的列表。
    • 遍历竣事后,哈希表的每个键值对即为一组异位词。

  • 为何用哈希表:异位词有一个共同点,即它们颠末排序后是类似的。哈希表可以用来快速归类类似“特性”的字符串。(也可以将字符串出现次数作为唯一特性键)
3. 最长一连序列(Longest Consecutive Sequence)


  • 问题描述:给定一个未排序的整数数组,找出最长一连序列,并且要求算法的时间复杂度为O(n)。
  • 哈希法思路:

    • 先把所有数字存入哈希表,然后再遍历这些数字。
    • 对于每个数字,判断其前一个数字是否在哈希表中,如果不在,则认为该数字是一个序列的起点,然后依次寻找后续的一连数字。
    • 通过哈希表,我们可以在 O(1) 时间内判断某个数字是否存在,从而使得整个过程可以在线性时间内完成。

  • 为何用哈希表:题目要求在 O(n) 时间内完成查找,哈希表能够在 O(1) 时间内判断一个数字是否存在,有效支持一连序列的查找。
总体总结:哈希法的应用思路

哈希表的焦点上风是快速查找和常数时间的操纵,当算法问题涉及到以下场景时,通常可以考虑哈希表:

  • 频繁查找元素是否存在: 当题目要求快速确定某个值是否已经存在于集合中,哈希表是非常适合的。
  • 快速查找某种关系匹配: 比如“找到符合某种和、差、乘积等条件的两个数”,这类问题通常可以利用哈希表举行配对。
  • 数据归类或分组:如果必要根据某种特性(比如字符串的排序形式、数字的特定属性等)来分组,哈希表可以用来高效管理和存储这些特性与对应的对象集合。焦点思路就是我们说的去找到唯一的键,通过其举行分组
  • 高效去重和统计: 如果题目必要对数据举行去重或频次统计,哈希表可以帮助你在遍历过程中以常数时间完成这些操纵。
在你思考如何优化暴力解法时,如果问题具有匹配查找、快速判断存在性或归类的特点,往往能快速联想到哈希表。

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

光之使者

金牌会员
这个人很懒什么都没写!
快速回复 返回顶部 返回列表