817. 链表组件：哈希表+flag

题目描述

这是 力扣上的 817. 链表组件，难度为 中等。

题目分析

做本题需要擦亮眼睛，题目给出了一个链表，里面的每一个节点对应的数字都是唯一的，还给出了一个 nums 数组，内容是链表的子集，那么也说明 nums 中的数据每一个数字也是唯一的

要求我们找到能在链表中连续的数字，且在 nums 数组中出现的数字，有几段？

思考：

如果不仔细看题，看到示例，我们是否会认为本题是要求我们找到符合要求的升序序列呢？不知道 xdm 第一次做这个题的时候，是否会被自己的潜意识给误导呢？

这也是心理学上大脑会对看到内容预测事情发展的走向，然后播放给我们看，最终导致我们还去处理数据排序的问题，其实完全没有必要哦

再次仔细看题，我们知道，题目没有对我们有排序的要求，最终问题我们可以简化到在链表中找到连续的数字，且出现在 nums 中的数字，总共有几段

那么对于这种题，我们第一时间应该要想到使用哈希表就能很好的应对了，

使用哈希表记录 nums 中已经存在的数字，然后去遍历链表，我们如何来记录是一个连续的段（并不一定是升序哦）呢？

我们可以引入一个标识，flag（初始化为 false），表示当前是否处于连续段中，且数字是存在与 nums 中

简单来说，就是

1. flag 从 false 跳变到 true 的时候，那么这就是一个新段的开始，
2. 如果 flag 是从 true 变成了 false ，那么这是一个段的结束，

如果 flag 从 true 到 true，那么仍然在段中，同理，flag 从 false 到 false 那就是在符合要求的段之外

• 遍历链表过程中，如果发现节点的数字是在 nums 中，且 flag 为 false 的时候，那么我们在结果处 +1，并将 flag 置为 true
• 如果当前遍历的节点数字不在 nums 中，那就将 flag 置为 false 即可

遍历完毕链表之后，直接返回结果

接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现

Golang 的实现方式：

• Golang 中 hash 表可以使用 map，咱们的键可以是 int，值可以任意定义

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func numComponents(head *ListNode, nums []int) (ans int) {
    help := make(map[int]struct{}, len(nums))
    for _, v := range nums {
        help[v] = struct{}{}
    }
    flag := false
    res := 0
    for head != nil{
    // 数据存在与 nums 中， 且 flag 为 false
        if _,ok := help[head.Val]; ok {
            if !flag {
                res++
                flag = true
            }
        }else{
            flag = false
        }
        head = head.Next
    }
    return res
}

这种实现方式，咱们的时间复杂度是 O(n)，n 是链表的节点个数，咱们遍历了一遍

空间复杂度是 O(m)，m 是 nums 数组的长度，咱们开辟了一个哈希表来存储 nums 中的数据

今天就到这里，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~